Online containers for hypergraphs, with applications to linear equations
JOURNAL OF COMBINATORIAL THEORY SERIES B
MetadataShow full item record
Saxton, D., & Thomason, A. (2016). Online containers for hypergraphs, with applications to linear equations. JOURNAL OF COMBINATORIAL THEORY SERIES B, 121 248-283. https://doi.org/10.1016/j.jctb.2016.05.011
A set of containers for a hypergraph G is a collection CC of vertex subsets, such that for every independent (or, indeed, merely sparse) set I of G there is some C∈CC∈C with I⊂CI⊂C, no member of CC is large, and the collection CC is relatively small. Containers with useful properties have been exhibited by Balogh, Morris and Samotij  and by the authors ;  ; , along with several applications. Our purpose here is to give a simpler algorithm than the one used in , which nevertheless yields containers with all the properties needed for the main container theorem of  and its consequences. Moreover this algorithm produces containers having the so-called online property, allowing the colouring results of  to be extended to all, not just simple, hypergraphs. Most of the proof of the container theorem remains the same if this new algorithm is used, and we do not repeat all the details here, but describe only the changes that need to be made. However, for illustrative purposes, we do include a complete proof of a slightly weaker but simpler version of the theorem, which for many (perhaps most) applications is plenty. We also present applications to the number of solution-free sets of linear equations, including the number of Sidon sets, that were announced in .
Hypergraph containers, Linear equations
External DOI: https://doi.org/10.1016/j.jctb.2016.05.011
This record's URL: https://www.repository.cam.ac.uk/handle/1810/264757