Graph structure via local occupancy
Preprint
Abstract
The first author together with Jenssen, Perkins and Roberts (2017) recently showed how local properties of the hard-core model on triangle-free graphs guarantee the existence of large independent sets, of size matching the best-known asymptotics due to Shearer (1983). The present work strengthens this in two ways: first, by guaranteeing stronger graph structure in terms of colourings through applications of the Lov\'asz local lemma; and second, by extending beyond triangle-free graphs in terms of local sparsity, treating for example graphs of bounded local edge density, of bounded local Hall ratio, and of bounded clique number. This generalises and improves upon much other earlier work, including that of Shearer (1995), Alon (1996) and Alon, Krivelevich and Sudakov (1999), and more recent results of Molloy (2019), Bernshteyn (2019) and Achlioptas, Iliopoulos and Sinclair (2019). Our results derive from a common framework built around the hard-core model. It pivots on a property we call local occupancy, giving a clean separation between the methods for deriving graph structure with probabilistic information and verifying the requisite probabilistic information itself.Keywords
All Related Versions
This publication has 43 references indexed in Scilit:
- Occupancy fraction, fractional colouring, and triangle fractionJournal of Graph Theory, 2021
- Dynamic concentration of the triangle‐free processRandom Structures & Algorithms, 2020
- 1-Subdivisions, the Fractional Chromatic Number and the Hall RatioCombinatorica, 2020
- Coloring triangle‐free graphs with local list sizesRandom Structures & Algorithms, 2020
- Asymptotically the List Colouring Constants Are 1Journal of Combinatorial Theory, Series B, 2002
- Coloring Graphs with Sparse NeighborhoodsJournal of Combinatorial Theory, Series B, 1999
- Independence numbers of locally sparse graphs and a Ramsey type problemRandom Structures & Algorithms, 1996
- On the independence number of sparse graphsRandom Structures & Algorithms, 1995
- A note on the independence number of triangle-free graphsDiscrete Mathematics, 1983
- On maximal paths and circuits of graphsActa Mathematica Hungarica, 1959