Online containers for hypergraphs, with applications to linear equations

详细信息    查看全文

• 作者：David Saxton ^{dwsaxton@gmail.com" class="auth_mail" title="E-mail the corresponding author} ; Andrew Thomason ^{a.g.thomason@dpmms.cam.ac.uk" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Hypergraph containers ; Linear equations
• 刊名：Journal of Combinatorial Theory, Series B
• 出版年：2016
• 出版时间：November 2016
• 年：2016
• 卷：121
• 期：Complete
• 页码：248-283
• 全文大小：686 K

文摘

A set of containers for a hypergraph G   is a collection C$\mathcal{C}$ of vertex subsets, such that for every independent (or, indeed, merely sparse) set I of G   there is some C∈C$C\in \mathcal{C}$ with I⊂C$I\subset C$, no member of C$\mathcal{C}$ is large, and the collection C$\mathcal{C}$ is relatively small. Containers with useful properties have been exhibited by Balogh, Morris and Samotij [6] and by the authors [39], [40] and [41], along with several applications.

Our purpose here is to give a simpler algorithm than the one used in [40], which nevertheless yields containers with all the properties needed for the main container theorem of [40] and its consequences. Moreover this algorithm produces containers having the so-called online property, allowing the colouring results of [40] 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 [40].