Uniform hypergraph ($|e|=r$)

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.