The connected-subgraph density conjecture for r-colorings

About 10 years old · traced to

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 r≥4r\geq4, every rr-coloring of K\NNK_\NN contains a monochromatic connected subgraph TT such that

dˉ(T)≥dˉS(T)≥1r−1.\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 r−1r-1 is a prime power.

References

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.