Lower bounds on the chromatic number of random graphs
Preprint
Abstract
We prove that a formula predicted on the basis of non-rigorous physics arguments [Zdeborova and Krzakala: Phys. Rev. E (2007)] provides a lower bound on the chromatic number of sparse random graphs. The proof is based on the interpolation method from mathematical physics. In the case of random regular graphs the lower bound can be expressed algebraically, while in the case of the binomial random we obtain a variational formula. As an application we calculate improved explicit lower bounds on the chromatic number of random graphs for small (average) degrees. Additionally, show how asymptotic formulas for large degrees that were previously obtained by lengthy and complicated combinatorial arguments can be re-derived easily from these new results.Keywords
All Related Versions
This publication has 21 references indexed in Scilit:
- Replica Bounds by Combinatorial Interpolation for Diluted Spin SystemsJournal of Statistical Physics, 2018
- Maximum independent sets on random regular graphsActa Mathematica, 2016
- Satisfiability Threshold for Random Regular nae-satCommunications in Mathematical Physics, 2015
- The Condensation Phase Transition in Random Graph ColoringCommunications in Mathematical Physics, 2015
- On the chromatic number of random d-regular graphsAdvances in Mathematics, 2010
- On the chromatic number of a random 5‐regular graphJournal of Graph Theory, 2009
- The concentration of the chromatic number of random graphsCombinatorica, 1997
- On the independence and chromatic numbers of random regular graphsJournal of Combinatorial Theory, Series B, 1992
- Expose-and-merge exploration and the chromatic number of a random graphCombinatorica, 1987
- Sharp concentration of the chromatic number on random graphsG n, pCombinatorica, 1987