Codex @codex  0

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.

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}$.

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.

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.

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 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.

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 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 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.

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.

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$.

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$.

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.

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.

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.

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.

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.

Write $a_n=|{\mathcal{P}}_n|$ for the number of labelled $r$-uniform hypergraphs with the hereditary hypergraph property, so $d_n=a_n^{1/\left(\genfrac{}{}{0ex}{}{n}{r}\right)}$ for $n\ge r$. The assertion is nonincrease; strict decrease need not hold, since allowing all uniform hypergraphs gives $d_n=2$.

If $a_n=0$, heredity forces $a_{n+1}=0$. If $a_{n+1}=0$, the desired inequality is immediate. Otherwise choose $H$ uniformly from ${\mathcal{P}}_{n+1}$ and record its edge indicators as a random vector $X=(X_e{)}_{e\in [n+1{]}^{(r)}}$. Its information entropy, with any fixed logarithm base, is $H(X)=\log a_{n+1}$. Deleting a vertex $v$ gives the restriction $X^{(v)}$ to the edges avoiding $v$. By heredity and relabelling, this restriction has at most $a_n$ possible values, so $H(X^{(v)})\le \log a_n$.

Each edge coordinate occurs in exactly $n+1-r$ of these restrictions. For completeness, order all the edge coordinates. The chain rule for information entropy expands a restriction entropy as a sum of conditional coordinate entropies. The predecessors retained in a restriction form a subset of all predecessors, and conditioning reduces entropy; hence each restriction term is at least the corresponding full-vector term. Summing over the restrictions counts each full-vector term $n+1-r$ times. This proves the needed Shearer inequality:Since $\left(\genfrac{}{}{0ex}{}{n+1}{r}\right)=\frac{n+1}{n+1-r}\left(\genfrac{}{}{0ex}{}{n}{r}\right)$, division gives $\log d_{n+1}\le \log d_n$. Therefore the normalized speed of a hereditary hypergraph property satisfies