Hypergraph containers

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

r

-uniform hypergraphs of average degree

d

have list chromatic number at least

(1 / (r - 1)^{2} + o (1)) l o g_{r} d

. For

r = 2

this improves a bound due to Alon and is tight. For

r g e 3

, previous bounds were weak but the present inequality is close to optimal. In the context of extremal graph theory, it follows that, for each

e l l

-uniform hypergraph

H

of order

k

, there is a collection

C

of

e l l

-uniform hypergraphs of order

n

each with

o (n^{k})

copies of

H

, such that every

H

-free

e l l

-uniform hypergraph of order

n

is a subgraph of a hypergraph in

C

, and

l o g | C | l e c n^{e l l - 1 / m (H)} l o g n

where

m (H)

is a standard parameter (there is a similar statement for induced subgraphs). This yields simple proofs, for example, for the number of

H

-free hypergraphs, and for the sparsity theorems of Conlon-Gowers and Schacht. A slight variant yields a counting version of the K{L}R 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.

Recommendations

Cites work

Cited in

(only showing first 100 items - show all)

This page was built for publication: Hypergraph containers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q496210)