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$.