Occupancy fraction, fractional colouring, and triangle fraction.

Given ε > 0 , there exists f 0 such that, if f 0 ≤ f ≤ Δ 2 + 1 , then for any graph G on n vertices of maximum degree Δ in which the neighbourhood of every vertex in G spans at most Δ 2 ∕ f edges, (i)an independent set of G drawn uniformly at random has at least ( 1 ∕ 2 - ε ) ( n ∕ Δ ) log f vertices in expectation, and(ii)the fractional chromatic number of G is at most ( 2 + ε ) Δ ∕ 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 and Shearer. The proofs use a tight analysis of the hard-core model.