2018/12/28 by Davies, Ewan, de Verclos, Rémi de Joannis, Kang, Ross J. +1 · 1 citation
#05C15 (Secondary) #05C35 #05D10 (Primary) #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR)
paper · doi:10.48550/arxiv.1812.11152
Given ε>0, there exists f0 such that, if f0 ≤ 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 (1981) and Shearer (1983). The proofs use a tight analysis of the hard-core model.