Hypergraph containers

• 成果类型: Article
• 署名作者: Saxton, David; Thomason, Andrew
• 署名单位: University of Cambridge
• 刊物名称: INVENTIONES MATHEMATICAE
• ISSN/ISSBN: 0020-9910
• DOI: 10.1007/s00222-014-0562-8
• 发表日期: 2015
• 页码: 925-992
• 关键词: turans extremal problem; hereditary properties; independent sets; removal lemma; Random graphs; number; systems; conjecture; colorings; subgraphs

摘要

We develop a notion of containment for independent sets in hypergraphs. For every -uniform hypergraph , we find a relatively small collection of vertex subsets, such that every independent set of is contained within a member of , and no member of is large; the collection, which is in various respects optimal, reveals an underlying structure to the independent sets. The containers offer a straightforward and unified approach to many combinatorial questions concerned (usually implicitly) with independence. With regard to colouring, it follows that simple -uniform hypergraphs of average degree have list chromatic number at least . For this improves a bound due to Alon and is tight. For , previous bounds were weak but the present inequality is close to optimal. In the context of extremal graph theory, it follows that, for each -uniform hypergraph of order , there is a collection of -uniform hypergraphs of order each with copies of , such that every -free -uniform hypergraph of order is a subgraph of a hypergraph in , and where is a standard parameter (there is a similar statement for induced subgraphs). This yields simple proofs, for example, for the number of -free hypergraphs, and for the sparsity theorems of Conlon-Gowers and Schacht. A slight variant yields a counting version of the KAR conjecture. Likewise, for systems of linear equations the containers supply, for example, bounds on the number of solution-free sets, and the existence of solutions in sparse random subsets. Balogh, Morris and Samotij have independently obtained related results.