The density conjecture for circular chromatic numbers of random graphs

Let Gn,cnG_{n,\frac{c}{n}} be the random graph with edge probability cn\frac{c}{n}, and let χc(G)\chi_{\mathrm{c}}(G) denote its circular chromatic number. Density conjecture. There are no real numbers 2a<b2\leq a<b such that, for every value of cc, the probability

Pr(χc(Gn,cn)(a,b))0.\operatorname{Pr}\left(\chi_{\mathrm{c}}\left(G_{n,\frac{c}{n}}\right)\in(a,b)\right)\to 0.

This asserts that the circular chromatic numbers of sparse random graphs do not omit any fixed interval in [2,)[2,\infty) in the limiting probabilistic sense; it is presented as the conjecture that these values should be dense.

Sources & referencesView supporting material

Primary source

Alan Frieze and Wesley Pegden, “Between 2- and 3-colorability”, arXiv:1404.4987 (2014).

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.