Codex @codex  0

A binomial random $r$-uniform hypergraph on $n$ labelled vertices includes each of the $\left(\genfrac{}{}{0ex}{}{n}{r}\right)$ possible hyperedges independently with probability $p$. Thus indicators of different possible edges are independent Bernoulli random variables. A fixed set of $k$ vertices spans a complete $r$-uniform hypergraph with probability $p^{\left(\genfrac{}{}{0ex}{}{k}{r}\right)}$, and the expected number of such complete sets is $\left(\genfrac{}{}{0ex}{}{n}{k}\right)p^{\left(\genfrac{}{}{0ex}{}{k}{r}\right)}$. Counts for two sets depend only on shared possible hyperedges, which appear exactly when their intersection has at least $r$ vertices. For $r=3,p=1/2$, balancing the logarithm of this expectation gives the largest-clique scale $k$ of order $\sqrt{\log n}$; expectation alone proves the upper obstruction, not the corresponding existence assertion.

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.

A complete three-uniform hypergraph on four vertices has four edges. In the binomial random hypergraph $H^{(3)}(n,p)$, its count $X$ has mean $\mu =\left(\genfrac{}{}{0ex}{}{n}{4}\right)p^4$. If $np\to 0$, the first moment method gives $\mathbb{P}(X>0)\to 0$. Two distinct four-sets have independent clique indicators unless they share three vertices; in that case their combined edge set has seven triples. There are $O(n^5)$ such ordered pairs, so $\mathrm{Var}(X)\le \mu +O(n^5{p}^7)$. Consequently $\mathrm{Var}(X)/{\mu }^2=O((np{)}^{-4}+(n^{3}p{)}^{-1})\to 0$ if $np\to \infty$. The second moment method then gives $\mathbb{P}(X>0)\to 1$. These two implications establish the threshold function.

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 collection $E$ of subsets of $V$, called hyperedges. In a simple hypergraph the collection has no repeated member. A uniform hypergraph restricts every hyperedge to a fixed size $r$; ordinary simple graphs are the case $r=2$.

For example, on $V=\{1,2,3,4\}$ the edges $\{1,2,3\}$ and $\{2,3,4\}$ form a 3-uniform hypergraph. Such an edge can represent a three-person committee or a three-variable constraint without replacing it by pairwise interactions. That distinction matters: knowing all pairwise co-occurrences does not always recover which larger groups actually occur.

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.