Density of monochromatic infinite subgraphs (Q2338615): Difference between revisions

The paper under review is concerned with complete infinite graphs with vertex set the natural numbers, where we assign a colour to each edge of the graph, and seek to find monochromatic (infinite) paths in this graph which have large density. We use two notions of density of a subset \(A\subseteq \mathbb{N}=V(G)\): the upper density is given by \(\overline{d}(A)=\limsup_{n\rightarrow\infty}\frac{\vert A\cap \{1,2,\ldots, n\}\vert}{n}\). We also consider the strong upper density; given an infinite sequence \(A=a_{1},a_{2},\ldots \) with \(A\subseteq \mathbb{N}\), we define \(\overline{d}_{s}(A)=\limsup_{n\rightarrow\infty}f(n)/n\), where \(f(n)=\sup\{m:\{a_{1},a_{2},\ldots ,a_{m}\}\subseteq \{1,2,\ldots, n\}\}\). Clearly \(\overline{d}_{s}(A)\leq \overline{d}(A)\) as the left-hand side only counts the density of unbroken initial segments of a path whereas the latter allows ``re-entry''.\par The first main result of this nice paper (Theorem 1.6) is that in every 2-colouring of the edges of the complete graph on \(\mathbb{N}\), \(K_{\mathbb{N}}\), there is a monochromatic path \(P\) with \(\overline{d}(P)\geq 3/4\). This improves an earlier result from \textit{P. Erdős} and \textit{F. Galvin} [Discrete Mathematics 113, 59--70 (1993; Zbl 0787.05071)] who proved a weaker version with \(3/4\) replaced by \(2/3\). The best known upper bound on the density, again from the earlier paper by Erdős and Galvin [loc. cit.], is 8/9 and the authors conjecture (Conjecture 8.1) that \(8/9\) is the correct answer. \par The second main result is that in every 2-colouring of the edges of \(K_{\mathbb{N}}\) there exists a monochromatic path with \(\overline{d}_{s}(P)\geq 2/3\). As Erdős and Galvin [loc. cit.] had proved in their earlier paper that there is a 2-colouring of the edges of \(K_{\mathbb{N}}\) in which every monochromatic path has \(\overline{d}_{s}(P)\geq 2/3\) this completely settles the question for strong density of a monochromatic path in \(K_{\mathbb{N}}\) with two colours. \par The authors also make remarks about cases with more colours, directed graphs and connected components more general than paths. A large range of techniques are used in the proofs. Several open problems are listed at the end of the paper.