Upper density of monochromatic infinite paths

Ramsey Theory investigates the existence of large monochromatic substructures. Unlike the most classical case of monochromatic complete subgraphs, the maximum guaranteed length of a monochromatic path in a two-edge-colored complete graph is well-understood. Gerencsér and Gyárfás in 1967 showed that any two-edge-coloring of a complete graph \(K_n\) contains a monochromatic path with \(\lfloor 2n/3\rfloor+1\) vertices. The following two-edge-coloring shows that this is the best possible: partition the vertices of \(K_n\) into two sets \(A\) and \(B\) such that \(|A|=\lfloor n/3\rfloor\) and \(|B|=\lceil 2n/3\rceil\), and color the edges between \(A\) and \(B\) red and edges inside each of the sets blue. The longest red path has \(2|A|+1\) vertices and the longest blue path has \(|B|\) vertices.

The main result of this paper concerns the corresponding problem for countably infinite graphs. To measure the size of a monochromatic subgraph, we associate the vertices with positive integers and consider the lower and the upper density of the vertex set of a monochromatic subgraph. The upper density of a subset \(A\) of positive integers is the limit superior of \(|A\cap\{1,...,\}|/n\), and the lower density is the limit inferior. The following example shows that there need not exist a monochromatic path with positive upper density such that its vertices form an increasing sequence: an edge joining vertices \(i\) and \(j\) is colored red if \(\lfloor\log_2 i\rfloor\not=\lfloor\log_2 j\rfloor\), and blue otherwise. In particular, the coloring yields blue cliques with 1, 2, 4, 8, etc., vertices mutually joined by red edges. Likewise, there are constructions of two-edge-colorings such that the lower density of every monochromatic path is zero.

A result of Rado from the 1970’s asserts that the vertices of any \(k\)-edge-colored countably infinite complete graph can be covered by \(k\) monochromatic paths. For a two-edge-colored complete graph on the positive integers, this implies the existence of a monochromatic path with upper density at least \(1/2\). In 1993, Erdős and Galvin raised the problem of determining the largest \(c\) such that every two-edge-coloring of the complete graph on the positive integers contains a monochromatic path with upper density at least \(c\). The authors solve this 25-year-old problem by showing that \(c=(12+\sqrt{8})/17\approx 0.87226\).