A hypergraph consists of a vertex set and a family of subsets of , called hyperedges. Unlike a graph, a hyperedge may contain more than two vertices. A uniform hypergraph restricts all hyperedges to one fixed size.
A polychromatic coloring of a hypergraph assigns colors to vertices so that every hyperedge contains all colors. It is stronger than merely requiring each hyperedge to be nonmonochromatic. Independently random colors and the Lovász local lemma can construct such colorings when edges are sufficiently large relative to their overlap degrees.
For finite , use vertices and hyperedges . Independent uniform -coloring gives missing-color probability at most , and the dependency graph of events has degree at most . For and , the symmetric Lovász local lemma condition holds. The compactness extension of the Lovász local lemma gives a coloring in which every translate contains every color.
Extremal hypergraph theory studies the largest or smallest possible size of a hypergraph under prescribed forbidden-subhypergraph or covering conditions. It generalizes extremal graph theory. The Turán density describes the asymptotic maximum edge proportion for a fixed uniform forbidden hypergraph.
With balanced cyclically ordered vertex classes and , include an -set if some start has at least vertices in its first classes for every . The cycle lemma implies every -set contains an edge. Its asymptotic density is ; taking the hypergraph complement gives a lower bound for the Turán density of a complete uniform hypergraph.
For a fixed -uniform forbidden hypergraph , its Turán density is the limit of . Averaging over smaller vertex subsets shows these normalized extremal numbers are nonincreasing, so the limit exists. For ordinary graphs, the Erdős-Stone theorem determines it from the chromatic number.
For the complete -uniform hypergraph , with , the bound is . In the complementary covering formulation, every -set containing an edge forces asymptotic edge density at least . It follows from clique-extension incidence inequalities and Cauchy-Schwarz inequality estimates on link degrees.
A multihypergraph has a multiset of hyperedges, allowing the same subset of vertices to appear more than once. Its hypergraph vertex degrees and hypergraph codegrees count multiplicity. Such multiplicity is important when several original hyperedges produce the same link in a hypergraph container theorem.
A subset of the vertices of a hypergraph is independent when no hyperedge lies wholly inside . This generalizes an independent set in an ordinary graph. If a hypergraph has ordinary graph edges as its vertices and forbidden copies as its hyperedges, these independent sets encode graphs without those forbidden copies.
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 permit a family of containers whose degree measures are bounded below one by a fixed amount. Each container has a container fingerprint of size . Iteration gives containers inducing at most an arbitrary fixed proportion of all hyperedges, with logarithmic family size . 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 , usually contained in a hypergraph independent set , which determines a container containing . A deterministic membership-query algorithm records positive answers in and uses negative answers to remove vertices from the container. Reconstruction from follows the golden rule for container algorithms.
The degree of a vertex in a hypergraph is the number of hyperedges containing . For a uniform hypergraph, summing degrees counts each hyperedge once for each of its vertices, so . In a multihypergraph, incidences are counted with multiplicity.
For a uniform hypergraph with positive average hypergraph vertex degree , the degree measure is . It is a probability measure and equals in a regular hypergraph. Every hypergraph independent set has degree measure at most , even when its fraction of all vertices is close to one.
The codegree of a vertex set in a hypergraph is the number of hyperedges containing every vertex in . For a singleton this is the hypergraph vertex degree; for two vertices it measures how often those vertices occur together. Subset codegrees of all sizes control the overlap relevant to the hypergraph container theorem.
A hypergraph is -uniform if each hyperedge has exactly vertices. Ordinary simple graphs are 2-uniform hypergraphs. Its average hypergraph vertex degree is .
The complete -uniform hypergraph on vertices contains every -subset of its vertex set. A hypergraph clique here means a restriction to a vertex subset of this form, rather than merely a clique in the pairwise shadow. For , it is an ordinary complete graph.
The complement of an -uniform hypergraph on has all -subsets of that are not hyperedges of the original hypergraph. An edge in every -set of one hypergraph is equivalent to the absence of a complete -uniform -vertex hypergraph in its complement.
Articles by others on the same topic
A hypergraph is a generalization of a graph in which an edge can connect any number of vertices, rather than just two. In a traditional graph, an edge is a connection between exactly two vertices. In contrast, a hypergraph allows an edge (often called a hyperedge) to link multiple vertices simultaneously.