Hypergraph ($H=(V,E)$)

A hypergraph consists of a vertex set $V$ and a family $E$ of subsets of $V$, called hyperedges. Unlike a graph, a hyperedge may contain more than two vertices. A uniform hypergraph restricts all hyperedges to one fixed size.

For a weighted hypergraph, the hypergraph cut function totals the weights of hyperedges meeting both a subset and its complement. It is a normalised set function and a symmetric set function. With nonnegative weights it is a nonnegative function and a submodular set function. It is generally not a monotone set function: a single two-element hyperedge of weight one has cut value one on either singleton, but zero on the whole ground set.

Proof of submodularity for nonnegative weights. For one hyperedge $e$ of size at least two, let $q_e$ indicate whether it is split. Adding $x\notin e$ has zero marginal increment. For $x\in e$, with $x\notin S$, the marginal increment is $1$ if $S\cap (e\setminus \{x\})$ is empty, $-1$ if it equals $e\setminus \{x\}$, and zero otherwise. These values can only decrease under inclusion of $S$. Thus diminishing returns holds for $q_e$, and taking a nonnegative weighted sum preserves it. For a singleton or empty hyperedge, $q_e$ is identically zero. A negative-weight two-element hyperedge gives a counterexample to submodularity: its two singleton values sum to a negative number, while the values at their union and intersection are zero.

A hypergraph with a specified numerical weight $w(e)$ for each hyperedge $e\in E$. In a hypergraph cut function, the weight records the cost or benefit of splitting a hyperedge between two sides. Signed weights and nonnegative weights lead to different submodularity properties.

A subhypergraph restricts the vertex set of a hypergraph and retains some of its edges contained in that vertex set. Retaining every such edge gives an induced subhypergraph.

For a subset $W$ of the vertex set of a hypergraph $H$, the induced subhypergraph retains exactly the edges wholly contained in $W$. This is the restriction used by a hereditary hypergraph property; it differs from intersecting every edge with $W$, which can change uniformity.

A matching in a hypergraph is a family of pairwise vertex-disjoint hypergraph edges. A perfect matching in a hypergraph covers every vertex; an almost-perfect matching in a hypergraph leaves a small proportion uncovered. In a proper edge colouring, each colour class is a matching in a hypergraph.

For a three-uniform hypergraph, the link of a vertex $v$ is the ordinary graph on the remaining vertices in which $xy$ is an edge precisely when $vxy$ is a hyperedge. Its edge count is the hypergraph vertex degree of $v$.

If $xyz$ is a hyperedge and the links of $x,y,z$ on four other vertices contain the three perfect matchings of a $K_4$, then those seven vertices contain a Fano plane. There is a second completion: if the link of $v$ contains three disjoint pairs, and the other six vertices contain all transversal triples through those pairs, take four triples of even parity and the three triples containing $v$. This again gives a Fano plane. These finite templates convert forbidden Fano copies into missing cross-part triples.

A proper hypergraph colouring assigns colours to the vertices of a hypergraph so that no hypergraph edge is monochromatic. Each colour class is a hypergraph independent set. This is often called weak colouring, to distinguish it from requiring every pair of vertices in each edge to have different colours.

The chromatic index of a hypergraph is the minimum number of colours needed to colour its edges so that intersecting edges have different colours. Each colour class is a matching in a hypergraph. It is at least the maximum hypergraph vertex degree, and at most $r(\Delta -1)+1$ for an $r$-uniform hypergraph of maximum degree $\Delta$, by greedily colouring edges: an edge meets at most $r(\Delta -1)$ others.

Given an $r$-uniform hypergraph $H$ and $K$ colours, construct an $(r+1)$-uniform auxiliary hypergraph with one task vertex for every $e\in E(H)$ and one resource vertex $(v,c)$ for every original vertex and colour. The assignment edge for $(e,c)$ contains the task $e$ and all resources $(v,c)$ with $v\in e$. A matching in a hypergraph of assignments is exactly a proper partial edge colouring. Task degrees are $K$; resource degrees are $d_H(v)$. Pairwise auxiliary hypergraph codegrees are at most $\max (1,{\max }_{v\ne w}{d}_H(v,w))$. Thus nearly equal original degrees and small original hypergraph codegrees transfer to the setting of a Rödl nibble. A locally balanced Rödl nibble must control the unmatched task count in every original star, not merely the total uncovered proportion.

A hypergraph has Property B if its vertices of a hypergraph can be coloured with two colours so that every hypergraph edge meets both colour classes. An $r$-uniform hypergraph with fewer than $2^{r-1}$ edges has Property B, by a fair independent colouring and the union bound. Conversely, for $r\ge 2$, take $N=2r^2$ vertices and independently sample $m=\lceil (N\log 2+1)2^r\rceil$ uniformly random $r$-subsets. In any fixed colouring an edge is monochromatic with probability at least $2^{-r}$: convexity of binomial coefficients reduces to the balanced colouring, and $\left(\genfrac{}{}{0ex}{}{r^2}{r}\right)/\left(\genfrac{}{}{0ex}{}{2r^2}{r}\right)\ge 2^{-r-1}$. The union bound over $2^N$ colourings gives a probability at most $2^N{e}^{-m{2}^{-r}}<1$ of any proper colouring. Removing repeated edges leaves a hypergraph without Property B and with $O(r^2{2}^r)$ edges.

A three-uniform hypergraph is bipartite when its vertex set has a partition into two parts such that every hyperedge meets both parts. All such triples on parts of sizes $a,b$ number $a\left(\genfrac{}{}{0ex}{}{b}{2}\right)+b\left(\genfrac{}{}{0ex}{}{a}{2}\right)=ab(a+b-2)/2$. For fixed total order this is maximized by balanced parts.

The hypergraph chromatic number is the minimum number of colours in a proper hypergraph colouring. If $H$ has $N$ vertices and maximum hypergraph independent set size $a$, then $\chi (H)\ge N/a$, since the colour classes partition its vertex set into hypergraph independent sets.

A hypergraph is linear when two distinct hypergraph edges intersect in at most one vertex of a hypergraph. Equivalently, every pair of distinct vertices of a hypergraph has hypergraph codegree at most one. This restricts local overlap without bounding the hypergraph chromatic number: the random alteration method gives linear three-uniform hypergraphs of arbitrarily large hypergraph chromatic number.

A vertex of a hypergraph $H=(V,E)$ is an element of its ground set $V$. Each hypergraph edge is a subset of $V$, and isolated vertices may belong to no edge. In a multipartite hypergraph, each vertex additionally lies in exactly one of the specified parts. This is the hypergraph analogue of a vertex of a graph, allowing edges of cardinality other than two.

For hypergraphs $F,H$, a labelled copy is an injective function $\varphi :V(F)\to V(H)$ taking every hypergraph edge of $F$ to an hypergraph edge of $H$. Specified vertex of a hypergraph classes may additionally require $\varphi (i)\in V_i$. The count is the sum, over these injective maps, of the product of the host hypergraph edge indicators. Without injectivity the same expression counts hypergraph homomorphisms. On a common host of size $n$, their counts differ by at most $\left(\genfrac{}{}{0ex}{}{|V(F)|}{2}\right)n^{|V(F)|-1}$: every noninjective map identifies at least one pair of abstract vertices of a hypergraph, each prescribed equality permits at most $n^{|V(F)|-1}$ maps, and the union bound completes the estimate. An induced copy additionally preserves nonedges, so its indicator product includes nonedge factors. The counting lemma for octahedrally quasirandom three-uniform hypergraphs estimates these labelled products when the requisite centered triple indicators have small box norm.

A multipartite hypergraph has a specified partition of its vertex of a hypergraph set into parts, and every hypergraph edge meets each part in at most one vertex of a hypergraph. For an $r$-uniform hypergraph with $r$ parts, an hypergraph edge chooses exactly one vertex of a hypergraph from each part; its indicator is therefore a function on the Cartesian product of those parts. A quadripartite three-uniform hypergraph instead has four possible types of hypergraph edge, according to the omitted part. A choice of one vertex of a hypergraph from each of its four parts is a three-uniform tetrahedron exactly when all four triples are hypergraph edges. Specifying the parts makes both subset density and labelled counting precise.

An edge of a hypergraph is one of its specified subsets of the vertex set. In a uniform hypergraph all edges have the same cardinality; unlike an ordinary edge of a graph, an edge may contain more than two vertices.

A colouring is polychromatic with $r$ colours if every hypergraph edge contains a vertex of every colour. This is stronger than requiring every edge to be nonmonochromatic. Under independent uniform colours, a $k$-element edge misses at least one of three colours with probability $3(2/3{)}^k-3(1/3{)}^k$. If each edge meets at most $m$ other edges, the edge-intersection dependency graph of events and the Lovász local lemma therefore give a polychromatic three-colouring whenever $e(m+1)[3(2/3{)}^k-3(1/3{)}^k]\le 1$.

Take every three-element subset of a four-element vertex set as a hypergraph edge. Any three-colouring repeats a colour on two vertices. A triple containing that pair cannot contain all three colours. Thus this uniform hypergraph has no polychromatic three-colouring, although each edge meets only three other edges.

A hypergraph isomorphism is a bijection of the vertex sets such that a subset is a hyperedge of the first hypergraph if and only if its image is a hyperedge of the second. The condition preserves both edges and nonedges. In the two-uniform case it is the usual relation of isomorphic graphs.

A hyperedge is a member of the edge family of a hypergraph. In an $r$-uniform hypergraph it is an $r$-element subset of the vertex set. For $r=2$ it is an ordinary edge of a graph. A simple hypergraph has no repeated hyperedges; a multihypergraph records multiplicities.

A polychromatic coloring of a hypergraph assigns $k$ colors to vertices so that every hyperedge contains all $k$ 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 $S\subset \mathbb{Z}$, use vertices $\mathbb{Z}$ and hyperedges $S+t$. Independent uniform $k$-coloring gives missing-color probability at most $k{e}^{-|S|/k}$, and the dependency graph of events has degree at most $|S|(|S|-1)$. For $k\ge 20$ and $|S|\ge 6k\log k$, 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.

For all sufficiently large $n$, the extremal number of the Fano plane as a three-uniform hypergraph is the displayed count of all triples crossing a balanced bipartition. The plane has no Property B, so this construction avoids it. A stability argument makes near-extremal Fano-free hypergraphs nearly bipartite; vertex deletion obtains high minimum degree. Optimizing the approximate bipartition and applying Fano completion through three matchings then rules out all internal triples. The large-order qualification matters: for $n=5,6$ the complete hypergraph has no Fano copy but exceeds the displayed count.

For every $\rho >0$, some $\delta >0$ makes every sufficiently large Fano-free three-uniform hypergraph of density at least $3/4-\delta$ admit a partition with at most $\rho n^3$ internal triples. The argument compares four hypergraph link graphs around a tetrahedron. Forbidden rainbow perfect matchings in their edge-coloured union force an approximate pattern with multiplicity two within the parts and four between them. A positive internal triple density would produce a complete tripartite six-vertex template, and its pairs together with a link vertex would complete a Fano plane.

With $r$ balanced cyclically ordered vertex classes and $2\le \ell \le r+1$, include an $\ell$-set if some start has at least $k+1$ vertices in its first $k$ classes for every $1\le k\le \ell -1$. The cycle lemma implies every $(r+1)$-set contains an edge. Its asymptotic density is $((\ell -1)/r{)}^{\ell -1}$; taking the hypergraph complement gives a lower bound for the Turán density of a complete uniform hypergraph.

For a fixed $\ell$-uniform forbidden hypergraph $F$, its Turán density is the limit of $\mathrm{ex}(n,F)/\left(\genfrac{}{}{0ex}{}{n}{\ell }\right)$. 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.

Normalized hypergraph extremal numbers decrease under vertex sampling and converge to Turán density. At a fixed sample size where the extremal density is close to that limit, excess density forces a positive fraction of samples to contain $H$. Counting incidences of copies and samples proves the displayed lower bound. Shrinking $\delta$ also handles the finitely many small orders when the required count is rounded down.

For the complete $\ell$-uniform hypergraph $K_r^{\ell }$, with $r\ge \ell \ge 2$, the bound is $\pi (K_r^{\ell })\le 1-1/\left(\genfrac{}{}{0ex}{}{r-1}{\ell -1}\right)$. In the complementary covering formulation, every $r$-set containing an edge forces asymptotic edge density at least $1/\left(\genfrac{}{}{0ex}{}{r-1}{\ell -1}\right)$. 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 $I$ of the vertices of a hypergraph is independent when no hyperedge lies wholly inside $I$. 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 $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.

The degree of a vertex $u$ in a hypergraph is the number of hyperedges containing $u$. For a uniform hypergraph, summing degrees counts each hyperedge once for each of its vertices, so ${\sum }_u{d}_H(u)=re(H)$. In a multihypergraph, incidences are counted with multiplicity.

For a uniform hypergraph with positive average hypergraph vertex degree $d$, the degree measure is $\mu (S)=(nd{)}^{-1}{\sum }_{u\in S}{d}_H(u)$. It is a probability measure and equals $|S|/n$ in a regular hypergraph. Every hypergraph independent set has degree measure at most $1-1/r$, even when its fraction of all vertices is close to one.

The codegree of a vertex set $\sigma$ in a hypergraph is the number of hyperedges containing every vertex in $\sigma$. 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 $r$-uniform if each hyperedge has exactly $r$ vertices. Ordinary simple graphs are 2-uniform hypergraphs. Its average hypergraph vertex degree is $r|E|/|V|$.

A property of uniform hypergraphs is hereditary if every induced subhypergraph of a hypergraph with that property also has the property. It is understood to be invariant under relabelling the vertex set. For example, excluding a specified induced hypergraph is hereditary. This permits counting restrictions to smaller vertex sets using the same counting function.

For a hereditary hypergraph property of $r$-uniform hypergraphs, ${\mathcal{P}}_n$ is the family on the labelled vertex set $[n]$. For $n\ge r$, its normalized speed lies between zero and two and is nonincreasing. Choose a uniformly random member on $n+1$ vertices and record its edge indicators. Each edge occurs in $n+1-r$ vertex-deletion restrictions. The Shearer inequality bounds its information entropy by the sum of the restriction entropies divided by $n+1-r$. Each restriction has at most $|{\mathcal{P}}_n|$ possible values. Division by $\left(\genfrac{}{}{0ex}{}{n+1}{r}\right)$ gives $\log d_{n+1}\le \log d_n$. Empty families are handled directly by heredity.

For a tripartite three-uniform hypergraph on nonempty finite parts $X,Y,Z$, let $h:X\times Y\times Z\to \{0,1\}$ be its hypergraph edge indicator, let $p=\mathbb{E}h$ and put $g=h-p$. In the eighth-power convention, $\alpha$-quasirandomness meansAll averages are uniform and independent, with repeated sampled vertices of a hypergraph allowed. This expression is nonnegative because it equals ${\mathbb{E}}_{x_0,x_1,y_0,y_1}({\mathbb{E}}_z{\prod }_{i,j}g(x_i,y_j,z){)}^2$. It measures correlations across the eight faces of a tripartite octahedral configuration. If instead the norm itself is used as the quasirandomness parameter, the parameter in this definition is its eighth power.

Let a fixed simple three-uniform hypergraph $F$ have $m$ hypergraph edges, with one host vertex of a hypergraph class $V_i$ for each vertex of a hypergraph. Assume each hypergraph edge triple has indicator $h_e$, subset density $p_e$, and balanced three-dimensional box norm at most ${\alpha }^{1/8}$. The normalized labelled hypergraph copy count is $\mathbb{E}{\prod }_{e\in E(F)}{h}_e$. Telescope this product against ${\prod }_e{p}_e$. In each error term, fix all variables outside the three vertices of a hypergraph of its balanced hypergraph edge. Every other hypergraph edge intersects that triple in at most two vertices of a hypergraph, so the remaining factors group into three pair functions bounded by one. The pair-factor correlation bound for the three-dimensional box norm bounds the error by ${\alpha }^{1/8}$. Summing givesFor the three-uniform tetrahedron, $m=4$. The same argument with a common host set counts homomorphisms; excluding collisions of distinct abstract vertices of a hypergraph changes the count by at most $\left(\genfrac{}{}{0ex}{}{|V(F)|}{2}\right)|V{|}^{|V(F)|-1}$.

The link at a fixed vertex $v$ of an $r$-uniform hypergraph has vertex set $V(H)\setminus \{v\}$ and the displayed $(r-1)$-element hyperedges. For a universal countable uniform hypergraph, its link has the hypergraph extension property: include $v$ in the finite set of vertices and prescribe only those $r$-edges containing $v$, completing the remaining prescription arbitrarily. Thus the link is a universal countable $(r-1)$-uniform hypergraph. In particular the link at a fixed vertex in the three-uniform case is the Rado graph. This operation retains a specified vertex; deleting the maximum from every edge is a different operation.

Choose each $r$-element subset of the natural numbers as a hyperedge independently with probability $p$, where $0<p<1$. This defines a countable random uniform hypergraph. For any finite pattern in the hypergraph extension property, an outside vertex realizes it with probability $q=p^{|\mathcal{A}|}(1-p{)}^{|(\genfrac{}{}{0ex}{}{S}{r-1})\setminus \mathcal{A}|}>0$. Distinct outside vertices use disjoint edge decisions, so the probability that the first $N$ candidates all fail is $(1-q{)}^N\to 0$. Taking a countable intersection over all finite patterns proves the extension property almost surely. The bounds $0<p<1$ are necessary for all patterns to have positive probability.

An $r$-uniform hypergraph has the extension property when, for every finite vertex set $S$ and every subfamily $\mathcal{A}\subseteq \left(\genfrac{}{}{0ex}{}{S}{r-1}\right)$, there is a vertex $v\notin S$ such that $F\cup \{v\}$ is a hyperedge exactly for $F\in \mathcal{A}$, among all $F\in \left(\genfrac{}{}{0ex}{}{S}{r-1}\right)$. Every prescribed pattern has infinitely many witnesses: enlarge $S$ by any finite set of witnesses already found and prescribe the original pattern on its old $(r-1)$-subsets, with arbitrary choices on the new ones. For $r=2$, this says that any finite adjacency and nonadjacency prescription has a new realizing vertex.

The universal countable uniform hypergraph is the unique, up to hypergraph isomorphism, countably infinite $r$-uniform hypergraph with the hypergraph extension property. To prove uniqueness, enumerate two such structures and construct finite partial hypergraph isomorphisms. Alternately add the least unused vertex of the first enumeration to the domain and the least unused vertex of the second to the range. Prescribe its incidences with every $(r-1)$-subset of the already matched vertices and apply the extension property in the other structure. The resulting union is a bijection preserving every hyperedge and nonedge. Existence follows from the countable random uniform hypergraph construction. A construction with only the forward steps embeds every countable $r$-uniform hypergraph as an induced subhypergraph, explaining the word universal. Its isomorphism type is independent of $p\in (0,1)$.

Label the vertices of a universal countable uniform hypergraph by the natural numbers and remove the largest vertex of each hyperedge. The resulting $(r-1)$-uniform hypergraph is complete. For any prescribed $(r-1)$-set $F$, apply the hypergraph extension property to a finite initial segment containing $F$, prescribing that $F$ extend to an edge. The resulting vertex is larger than every member of $F$, so this deletion produces $F$. This supplies a useful example of a projection that destroys the nonedge information of a random structure.

Strong regularity refines both the vertex classes and the pair graphs supporting triple hyperedges. The resulting triads in a hypergraph regularity partition have nearly constant relative triple density outside a small exceptional weight. Pair and triple errors must be chosen in a hierarchy strong enough for a relative tetrahedron counting lemma; ordinary graph regularity on the vertex partition alone is insufficient. Refinement raises bounded conditional-density energies.

A triad is the set of triples supported on one prescribed pair cell for each of the three pairs of vertex classes. Relative triple density is measured among those supported triples. In strong hypergraph regularity, the pair cells must themselves be sufficiently regular and have controlled density before a small relative three-dimensional box norm can give a tetrahedron counting lemma.

A sufficiently regular four-partite three-uniform hypergraph, supported on sufficiently regular pair cells of positive density and with positive relative triple densities, has a positive fourth-power number of three-uniform tetrahedra. On complete pair supports, telescoping the four edge functions shows that an error of at most $\xi$ in each three-dimensional box norm gives a counting error at most $4\xi$. The relative version additionally requires control of the pair-support densities.

For each fixed finite uniform hypergraph $F$, having few copies of $F$ forces small edge-edit distance from an $F$-free hypergraph. More precisely, for every $\eta >0$ there is $\rho >0$ such that fewer than $\rho v^{|V(F)|}$ copies can be eliminated by deleting fewer than $\eta v^r$ edges in an $r$-uniform hypergraph. Strong regularity for three-uniform hypergraphs and a relative counting lemma prove the case $r=3$.

For every $\eta >0$, some $\rho >0$ has this property: a three-uniform hypergraph on $v$ vertices with fewer than $\rho v^4$ copies of the three-uniform tetrahedron can be made tetrahedron-free by removing fewer than $\eta v^3$ hyperedges. The four-term progression hypergraph encoding converts this into the length-four case of the Szemerédi theorem.

The complete $\ell$-uniform hypergraph on $r$ vertices contains every $\ell$-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 $\ell =2$, it is an ordinary complete graph.

An $r$-uniform hypergraph is strongly saturated with respect to a complete uniform hypergraph of order $r+t$ when every missing edge immediately completes such a clique. Existing cliques are allowed. All $r$-sets meeting a fixed $t$-set give an example: the witness for a missing edge is its union with that fixed set. It has $\left(\genfrac{}{}{0ex}{}{n}{r}\right)-\left(\genfrac{}{}{0ex}{}{n-t}{r}\right)$ edges, and the exterior-power quotient bound for strong hypergraph saturation proves optimality.

Take $U$ to be the kernel of a $t$-row Vandermonde matrix on distinct coordinates. For each $(r+t)$-set $T$, $U$ intersects its coordinate subspace in dimension $r$. Wedge a basis of that intersection: its coefficient on every $r$-subset of $T$ is nonzero, because projection onto that subset is an isomorphism by independence of the complementary $t$ columns. Modulo the exterior power of $U$, this gives a dependence involving every clique edge with nonzero coefficient. Strong saturation expresses every missing-edge vector in the span of present ones. Since all coordinate-edge vectors span the quotient, edge count is at least its dimension.

The three-uniform tetrahedron is the hypergraph on four vertices with all four possible triple hyperedges. It is the complete uniform hypergraph $K_4^3$, and differs from its geometric realization as a tetrahedron. Its edge pattern encodes four-term arithmetic progressions.

The complement of an $\ell$-uniform hypergraph on $V$ has all $\ell$-subsets of $V$ that are not hyperedges of the original hypergraph. An edge in every $r$-set of one hypergraph is equivalent to the absence of a complete $\ell$-uniform $r$-vertex hypergraph in its complement.