Ewan S. D. Davies

Random independent sets and local sparsity

We analyze random constructions of independent sets in locally sparse graphs, specifically graphs with bounded maximum average degree in neighborhoods or with fractionally $r$-colorable neighborhoods. Specializing our methods to finding large independent sets and low-weight fractional colorings, we focus on optimizing...