Correspondence Colouring of Random Graphs
summary
Erdős–Rényi G(n,p) with constant p has correspondence chromatic number O(n/√log n), proved by giving a sufficient condition (a numbers of independent sets richness) and then showing random graphs meet it; the proof uses concentration inequalities and a guided Lovász Local Lemma argument on random partial colorings. The authors conjecture the true rate is O(n/log n) based on random correspondence assignments; the constructive probabilistic method yields the stated bound but leaves the conjectured improvement open.
AI-written summary · about
chapters (10)
- 0:00Introduction to the topic
- 1:25Defining correspondence coloring
- 6:35Examples and comparisons
- 14:19Known bounds and literature
- 19:38Random graph conjecture
- 23:16Hadwiger's conjecture links
- 28:44Structural graph theory context
- 38:05The richness lemma
- 45:31Recovering known results
- 50:52Probabilistic proof sketch
related talks
55mSiegel's Theorem, Edge Coloring, and a Holant Dichotomy
01h 02mFine-Grained Counting Complexity II
29mColor Coding-Related Techniques
01h 02mFine-Grained Counting Complexity I
06mThe 5 Colour Theorem
23mWorst-Case to Expander-Case Reductions
33mLower Bounds for Subexponential Parameterized Complexity of Minimum Fill-in and Related Problems
38mLower Bounds on the Space Complexity of Dynamic Programming