论文标题
边彩色无限完整图和两部分图中单色路径的上部密度
Upper density of monochromatic paths in edge-coloured infinite complete graphs and bipartite graphs
论文作者
论文摘要
带有$ v（g）\ subseteq \ mathbb {n} $的无限图$ g $的上部密度定义为$ \ overline {d}（g）= \ limsup_ {n \ rightArrow \ rightArrow \ rightarrow \ infty \ infty} {| v（g）令$ k _ {\ mathbb {n}} $为无限完整的图形，带顶点set $ \ mathbb {n} $。 Corsten，Debiasio，Lamaison和Lang表明，在每2美元的$ k _ {\ Mathbb {n}} $中，存在一个至少$（12 + \ sqrt {8}}）/17 $的单色路径。在本文中，我们将此结果扩展到$ k _ {\ mathbb {n}} $ $ k \ ge 3 $的$ k $ - edge-彩色。我们推测，每个$ k $ edge颜色的$ k _ {\ mathbb {n}} $都包含一个至少$ 1/（k-1）$的单色路径，这是最好的（当$ k-1 $是主要功率时）。我们证明，当$ k = 3 $且在$ k = 4 $时渐近时，这是正确的。此外，我们表明可以从其双方变体中得出这个问题，这是独立的。
The upper density of an infinite graph $G$ with $V(G) \subseteq \mathbb{N}$ is defined as $\overline{d}(G) = \limsup_{n \rightarrow \infty}{|V(G) \cap \{1,\ldots,n\}|}/{n}$. Let $K_{\mathbb{N}}$ be the infinite complete graph with vertex set $\mathbb{N}$. Corsten, DeBiasio, Lamaison and Lang showed that in every $2$-edge-colouring of $K_{\mathbb{N}}$, there exists a monochromatic path with upper density at least $(12 + \sqrt{8})/17$, which is best possible. In this paper, we extend this result to $k$-edge-colouring of $K_{\mathbb{N}}$ for $k \ge 3$. We conjecture that every $k$-edge-coloured $K_{\mathbb{N}}$ contains a monochromatic path with upper density at least $1/(k-1)$, which is best possible (when $k-1$ is a prime power). We prove that this is true when $k = 3$ and asymptotically when $k =4$. Furthermore, we show that this problem can be deduced from its bipartite variant, which is of independent interest.
