Hypergraph container ($I\subseteq C\in \mathcal{C}$)

A container family is a collection of vertex subsets such that every hypergraph independent set lies in at least one member. A useful family has few members and each member is small in hypergraph degree measure or induces few hyperedges. Container fingerprints encode the members and permit bounds on the number of independent sets.

For fixed uniformity, sufficiently small nonsingleton hypergraph codegrees relative to $d{\tau }^{|\sigma |-1}$ permit a family of containers whose degree measures are bounded below one by a fixed amount. Each container has a container fingerprint of size $O(\tau n)$. Iteration gives containers inducing at most an arbitrary fixed proportion of all hyperedges, with logarithmic family size $O(n\tau \log (1/\tau ))$. The constants depend on the uniformity and desired edge proportion, and the average degree must be positive.

A container algorithm may use membership in the unknown independent set only through information recorded in its container fingerprint. With a deterministic ordering and deterministic tests, record every positive queried vertex; queried negative vertices can be excluded. All state updates must be recoverable from the fingerprint alone, so replaying the algorithm constructs a container without knowing the independent set.

A container fingerprint is a small vertex subset $T$, usually contained in a hypergraph independent set $I$, which determines a container $C(T)$ containing $I$. A deterministic membership-query algorithm records positive answers in $T$ and uses negative answers to remove vertices from the container. Reconstruction from $T$ follows the golden rule for container algorithms.