![Analysis and TCS_hi-res_logo](/sites/default/files/styles/workshop_banner_sm_1x/public/2023-02/Analysis%20and%20TCS_hi-res.png.jpg?itok=HyceKiAM)
Abstract
We show that Erdős-Renyi random graph with constant density has correspondence chromatic number O(n/\sqrt{logn}); this matches a prediction from linear Hadwiger’s conjecture for correspondence colouring. The proof follows from a sufficient condition for correspondence colourability in terms of the numbers of independent sets. We conjecture the truth to be of order O(n/logn) as suggested by the random correspondence assignment. This is joint work with Zdenek Dvorak.