Fractional colorings of $K_r$-free graphs with local demands

Abstract

We study fractional coloring with local demands, a framework introduced by Kelly and Postle in which one seeks a probability distribution on the independent sets of a graph such that each vertex $v$ is included with probability at least a prescribed target $\varphi (v)$. For $K_r$-free graphs, Kelly and Postle conjectured that such a distribution exists provided $\varphi (v)\le c_r\frac{\log d(v)}{d(v)}$ for a fixed \(c_r>0\), where $d(v)$ is the degree of $v$, and they established this up to a factor of $(\log \log d(v){)}^2$. In this paper, we prove their conjecture, showing that \[ ϕ(v)\le\frac{c}{r}\frac{\log(d(v)+2)}{d(v)+1} \] suffices for an absolute constant $c>0$. As a corollary, we obtain a lower bound on the independence number of $K_r$-free graphs in terms of their degree sequence. This strengthens the bound that OpenAI proved in resolving the Ajtai-Erdős-Komlós-Szemerédi conjecture. Moreover, our argument yields a deterministic algorithm that produces the desired probability distribution in time $2^{O(r^2)}{n}^{O(1)}$, where \(n\) is the number of vertices and the implied constants are absolute.

arXiv comment60 pages