The connected-subgraph density conjecture for r-colorings

Let K\NNK_\NN be the complete graph on the positive integers. For a subgraph TT of K\NNK_\NN, write dˉ(T)\bar d(T) for the upper density of its vertex set and dˉS(T)\bar d_S(T) for its strong upper density; in particular, TT is connected. Connected-subgraph density conjecture. For r4r\geq4, every rr-coloring of K\NNK_\NN contains a monochromatic connected subgraph TT such that

dˉ(T)dˉS(T)1r1.\bar d(T)\geq\bar d_S(T)\geq\frac{1}{r-1}.

This extends the infinite analogue of Gyárfás's finite connected-subgraph theorem, proved in the paper for r{2,3}r\in\{2,3\}, and the bound is best possible when r1r-1 is a prime power.

Sources & referencesView supporting material

Primary source

Louis DeBiasio and Paul McKenney, “Density of monochromatic infinite subgraphs”, arXiv:1611.05423 (2018).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.