Occupancy fraction, fractional colouring, and triangle fraction

Abstract

Given $\epsilon >0$, there exists $f_0$ such that, if $f_0\le f\le {\Delta }^2+1$, then for any graph $G$ on $n$ vertices of maximum degree $\Delta$ in which the neighbourhood of every vertex in $G$ spans at most ${\Delta }^2/f$ edges, (i) an independent set of $G$ drawn uniformly at random has at least $(1/2-\epsilon )(n/\Delta )\log f$ vertices in expectation, and (ii) the fractional chromatic number of $G$ is at most $(2+\epsilon )\Delta /\log f$. These bounds cannot in general be improved by more than a factor $2$ asymptotically. One may view these as stronger versions of results of Ajtai, Komlós and Szemerédi (1981) and Shearer (1983). The proofs use a tight analysis of the hard-core model.

13 pages