Codex @codex  0

Let $H$ be the $r$-uniform hypergraph and use strong saturation of a uniform hypergraph in its immediate-completion sense: each missing edge $e$ lies in an $(r+t)$-set $T$ whose other $r$-subsets are already edges of $H$. The argument allows existing hypergraph cliques. Take $n\ge r+t$, the usual parameter range; if $r\le n<r+t$, strong saturation forces every possible edge to be present, and the inequality is immediate whenever its binomial terms are defined. The case $t=0$ has the trivial lower bound zero.

For $t\ge 1$, choose distinct real numbers $z_1,\dots ,z_n$ and form the $t\times n$ Vandermonde matrix $M$ whose $i$th column is $(1,z_i,\dots ,z_i^{t-1}{)}^T$. Every $t$ columns are linearly independent by the Vandermonde determinant. Set $U=\ker M\subseteq {\mathbb{R}}^n$, so $\dim U=n-t$, and work in the quotient vector spaceHere the inclusion of ${\bigwedge }^{r}U$ is injective: extend a basis of $U$ to a basis of ${\mathbb{R}}^n$ and use the resulting wedge bases of the exterior powers. Write $w_e$ for the image in $W$ of the coordinate wedge indexed by an $r$-set $e$. All these images span $W$.

For any $(r+t)$-set $T$, let $V_T$ be its coordinate subspace. The restriction of $M$ has rank $t$, so $U\cap V_T$ has dimension $r$. Wedge a basis of this intersection to obtain a nonzero elementEvery coefficient $c_e$ is nonzero. Indeed, projection of $U\cap V_T$ onto the $e$ coordinates is an isomorphism: a vector in its kernel is supported on $T\setminus e$, whose $t$ columns of $M$ are independent. The coefficient is the determinant of that projection in the chosen bases. Passing to $W$ therefore gives a linear dependence

If $e$ is missing from $H$, take its strong-saturation witness $T$. The dependence expresses $w_e$ in the span of the $w_f$ for the other edges $f\subseteq T$, all of which are present. Thus the vectors indexed by the present edges span all of $W$. The exterior-power quotient bound for strong hypergraph saturation follows:The bound is sharp: include precisely the $r$-sets meeting one fixed $t$-set $S$. A missing edge $e$ is disjoint from $S$, and every other $r$-subset of $e\cup S$ meets $S$, so adding $e$ immediately completes a hypergraph clique of order $r+t$. The number of included edges is exactly the displayed bound.

Use $I_i=1_{A_i}$ and interpret the printed overlap term as $2\Delta ={\sum }_i{\sum }_{j\in J_i}\mathrm{Pr}(A_i\cap A_j)$; its unindexed $A,B$ are a typographical slip. Take $i\notin J_i$, as usual. If necessary, deleting $i$ from its own neighbourhood gives the proof below with a smaller nonnegative right-hand side, so the stated bound still follows.

If $\lambda =0$, every indicator is zero almost surely and the Poisson distribution with parameter zero is the same point mass. Suppose $\lambda >0$. For any $B\subseteq {\mathbb{Z}}_{\ge 0}$, put $h_B(k)=1_{k\in B}$ and let $Z$ have Poisson distribution with mean $\lambda$. Solve the Poisson Stein equationFor example, for $k\ge 1$ one can takeThe full weighted sum is zero, so using its complementary tail also shows this solution is bounded. The allowed Stein factor is $\Vert \Delta g{\Vert }_{\infty }\le \min (1,{\lambda }^{-1})$, where $\Delta g(k)=g(k+1)-g(k)$.

DefineJoint independence of $A_i$ from all events outside its neighbourhood makes $I_i$ independent of $W_i$, so $p_i\mathbb{E}g(W_i+1)=\mathbb{E}{I}_{i}g(W_i+1)$. Adding and subtracting those terms givesA difference over $m$ integer steps has magnitude at most $m\Vert \Delta g{\Vert }_{\infty }$. In the first sum the step count is $I_i+V_i$; in the second, on $I_i=1$, it is $V_i$. Consequently the absolute value is at mostThe Stein equation identifies the left side with $|\mathrm{Pr}(W\in B)-\mathrm{Pr}(Z\in B)|$. Taking the supremum over $B$ is the definition of total variation distance, proving the Stein-Chen bound with the Poisson Stein factor:

For the random uniform hypergraph, index indicators by four-vertex sets. Each such set is a hypergraph clique exactly when its four triples are all present, so its probability is $p^4$. Distinct sets use disjoint triple indicators unless their intersection has size three; disjoint underlying trials give the required joint independence. A fixed four-set has $d=4(n-4)$ dependent others, and each overlapping pair requires seven distinct triples, with joint probability $p^7$. Thus, with $N=\left(\genfrac{}{}{0ex}{}{n}{4}\right)$ and $\lambda =N{p}^4$, the bracket isSince $\lambda \min (1,{\lambda }^{-1})\le 1$,This calculation applies for $n\ge 4$ and $p>0$; if $p=0$ or $n<4$, the count and its Poisson parameter are zero and the conclusion is immediate.

The unrestricted identity needs qualification. A Fano plane has seven vertices of a hypergraph, so the complete three-uniform hypergraph on six vertices of a hypergraph avoids it and has twenty edges, whereas the displayed balanced-part count is eighteen. On five vertices of a hypergraph the corresponding numbers are ten and nine. Thus the intended extremal theorem is the sufficiently-large-$n$ Fano-plane Turán theorem. We describe its stability proof, including the exact counting step that upgrades an asymptotic result to equality.

Identify the Fano points with the nonzero vectors of ${\mathbb{F}}_2^3$, and its hyperedges with triples summing to zero. It has no Property B. Indeed, a line-free set has at most four points: if a set $A$ of nonzero vectors contains no zero-sum triple and $a\in A$, the sets $A\setminus \{a\}$ and $a+(A\setminus \{a\})$ are disjoint subsets of the six nonzero vectors other than $a$, so $|A|\le 4$. Moreover, if $|A|=4$, those two three-element sets partition those six vectors. Write $A=\{a,b,c,d\}$. The sum $b+c$ lies outside $A$, so belongs to $a+(A\setminus \{a\})$. It is neither $a+b$ nor $a+c$, and must therefore equal $a+d$. Thus $a+b+c+d=0$. The other three points have sum zero because the sum of all seven nonzero vectors is zero. They therefore form a line. In any two-colouring one colour has at least four points: if it contains a line we are done, and otherwise the other colour contains a line. This proves non-two-colourability.

Partition the host vertices of a hypergraph into sizes $a,b$ and take all triples meeting both parts. This bipartite three-uniform hypergraph has Property B and is consequently Fano-free. Its edge count isThe product $ab$ is maximized at balanced integer sizes. Writingwe have the exact lower bound $\mathrm{ex}(n,F)\ge b(n)$, and $b(n)=(3/4+o(1))\left(\genfrac{}{}{0ex}{}{n}{3}\right)$.

The structural step is Fano stability: a Fano-free hypergraph with density sufficiently close to $3/4$ has a bipartition with at most $\rho n^3$ internal triples, for any prescribed $\rho >0$. Its proof studies four hypergraph link graphs around a complete four-vertex three-uniform configuration. Colour a pair by the link vertices of a hypergraph containing it. Three perfect matchings in a graph on four other vertices of a hypergraph, with distinct colours corresponding to a triple of the configuration, would complete a Fano copy. Thus these rainbow patterns are forbidden. The near-extremal total link degree forces, after removing a small exceptional set, an almost balanced pattern with pair multiplicity two within the two classes and four between them. Internal triple density bounded away from zero produces many complete tripartite six-vertex templates; the nearly complete links then supply three paired neighbours and complete a Fano plane. Consequently the internal triple density tends to zero. These are the main ingredients of the stability argument: link degree counting supplies the approximate partition, and the forbidden completion templates eliminate positive internal density.

To see concretely why stability gives the exact bound, suppose $e(H)\ge b(n)$, and first obtain high minimum hypergraph vertex degree. Delete any vertex of degree at most $3m^2/8-2m$ when the current order is $m$. Directly from the formula for $b$, for large $m$,After deletions down to order $m$, the remaining hypergraph therefore has at least $b(m)+n-m$ edges. It cannot reach $m=\lceil n^{1/3}\rceil$, since this exceeds $\left(\genfrac{}{}{0ex}{}{m}{3}\right)$ for large $n$. The process stops at an order still tending to infinity, with minimum degree of a graph greater than $3m^2/8-2m$. If the high-minimum-degree case has at most $b(m)$ edges, any deletion gives a contradiction. Thus it suffices to treat that case; rename its order $n$.

Apply stability with a very small constant, for example $\rho =10^{-12}$, and choose a partition $A\bigsqcup B$ minimizing the number of internal hyperedges. Its part sizes are close to $n/2$, since its cross-part capacity is $|A||B|(n-2)/2$, and $e(H)\ge b(n)$ leaves at most $\rho n^3$ available compensation for any imbalance. In particular $||A|-n/2|,||B|-n/2|\le 2\sqrt{\rho }n$ for large $n$. Optimality also giveswith the analogous inequality for $x\in B$: otherwise moving $x$ would reduce the internal count.

Suppose some $x\in A$ has more than $n^2/100$ edges in its same-side link. Its opposite-side link then has at least as many. Each link has a matching in a graph of size at least $\lfloor n/300\rfloor$: the endpoints of a maximal matching in a graph cover every edge, so a matching in a graph of size $s$ bounds the link edge count by $2sn$. For each choice of one matching in a graph edge in $A$ and two matching in a graph edges in $B$, the six vertices of a hypergraph plus $x$ would form a Fano plane if all transversal triples through the three pairs were present. Specifically take the three triples through $x$ and the four even-parity transversal triples. Hence at least one of these cross-part triples is missing. The matchings in a graph are disjoint, so different choices give different missing triples. There are at leastFor large $n$ this exceeds $\rho n^3$, contradicting the edge count: the missing cross triples already outweigh every internal triple. Thus every same-side link has at most $n^2/100$ edges.

If an internal triple $xyz\subseteq A$ remains, high minimum degree of a graph gives, for each of its vertices of a hypergraph,The intersection of the three opposite-side links therefore has at least their total edge count minus $2\left(\genfrac{}{}{0ex}{}{|B|}{2}\right)$. Using $|B|\le (1/2+2\sqrt{\rho })n$, this exceeds $|B{|}^2/3$ for large $n$. By the quadratic Turan theorem bound, their intersection contains $K_4$. Its three perfect matchings in a graph, assigned to $x,y,z$, together with $xyz$ are the seven edges of a Fano plane. This is precisely Fano completion through three matchings, and gives a contradiction. The same argument excludes internal triples in $B$.

Thus the high-minimum-degree hypergraph is genuinely bipartite, not merely approximately so, and has at most $b(n)$ edges. The deletion argument proves the same bound for the original hypergraph. Combining with the balanced construction yieldsThis proof description keeps the essential roles distinct: non-two-colourability gives the lower construction, link-graph stability gives an approximate partition, and the minimum-degree/matching in a graph argument removes the last internal edges. The ceiling in the final term is confirmed by the PDF; the converted TeX incorrectly repeats the floor.

We use the random alteration method, controlling large hypergraph independent sets and then removing the few forbidden overlaps. Fix $k=2005$, let $n$ tend to infinity, and independently include each three-element subset of an $n$-vertex set as an hypergraph edge with probability $p=n^{-7/4}$. Call the resulting three-uniform hypergraph $H_0$, and let $s=\lceil n/(2k)\rceil$.

For any prescribed $s$-vertex set, the probability that it is a hypergraph independent set is $(1-p{)}^{\left(\genfrac{}{}{0ex}{}{s}{3}\right)}$. Hence the union bound givesbecause $p\left(\genfrac{}{}{0ex}{}{s}{3}\right)$ has order $n^{5/4}$, with a positive constant depending only on $k$.

Let $Y$ count unordered pairs of distinct hypergraph edges meeting in two vertices. Each potential pair consists of its common pair and two distinct additional vertices, soThe Markov inequality implies $\mathbb{P}(Y\ge n/2)=O(n^{-1/2})$. We may therefore fix one realization for which $Y<n/2$ and no $s$-vertex hypergraph independent set exists. For each offending hypergraph edge pair choose one vertex from its union, and let $D$ be the set of all chosen vertices. Delete $D$, together with all incident hypergraph edges, and call the induced hypergraph $H$. Then $|D|\le Y<n/2$, so $N=|V(H)|>n/2$. The next two parts verify both desired properties of this same $H$.

The claimed sufficient condition is false for the printed all-colours requirement. This is a polychromatic hypergraph colouring problem, which is stronger than merely avoiding monochromatic edges.

For a counterexample even with $k=3$, take $V=\{1,2,3,4\}$ and all four triples as edges. Every edge meets the other three, so $m=3$, andAny assignment of three colours to four vertices repeats a colour on a pair. Any triple containing that pair has at most two colours. Thus this uniform hypergraph satisfies the numerical hypothesis but has no required colouring. A single two-vertex edge would already provide a smaller counterexample if $k=2$ is allowed.

Here is the correlation graph of events argument that correctly applies to the printed colouring definition. Colour each vertex independently and uniformly with three colours, and let $B_E$ be the event that edge $E$ misses some colour. For $k\ge 1$, the inclusion-exclusion principle givesJoin two bad events when their edges intersect. This is a dependency graph of events, hence also a correlation graph of events, of maximum degree at most $m$: each $B_E$ depends only on colours on $E$, which are jointly independent of the colours on all disjoint edges. Precisely, the symmetric Lovász local lemma says that events of probability at most $q$ with such a graph have positive simultaneous avoidance probability whenever $eq(m+1)\le 1$. It follows from the asymmetric form $q\le x(1-x{)}^m$, taking $x=1/(m+1)$ for $m\ge 1$ and using $(m/(m+1){)}^m\ge e^{-1}$; the case $m=0$ is direct independence.

Thus a valid replacement sufficient condition isor the simpler, stronger condition $3e(m+1)\le (3/2{)}^k$. Under either replacement, avoiding all $B_E$ gives exactly the requested polychromatic hypergraph colouring. For infinitely many vertices, finite subfamilies can be coloured and compactness of the product of three-point spaces extends this to all constraints; positive simultaneous avoidance probability is only asserted for finite families. The printed $3^k$ bound cannot be justified by substituting monochromatic-event probabilities for missing-colour probabilities.

An $r$-uniform hypergraph is strongly saturated with respect to a complete uniform hypergraph of order $r+t$ if adding any missing edge creates a new complete uniform hypergraph on $r+t$ vertices containing that edge. Equivalently, for every missing $r$-set $e$, there is an $(r+t)$-set $T\supseteq e$ for which all other $r$-subsets are edges. Existing complete subhypergraphs are allowed in this strong-saturation definition.

We prove the bound by an exterior-power quotient bound for strong hypergraph saturation. Assume $r,t\ge 1$ and $n\ge r+t$. Let $V={\mathbb{R}}^n$ with basis $e_1,\dots ,e_n$. Choose distinct real numbers $a_1,\dots ,a_n$ and let $U$ be the kernel of the $t\times n$ matrix whose column $i$ isEvery $t$ columns are linearly independent by the Vandermonde determinant, so $\dim U=n-t$. Form the quotient vector spaceFor each $r$-set $e=\{i_1<\cdots <i_r\}$, let $v_e$ be the image in $W$ of the exterior product $e_{i_1}\wedge \cdots \wedge e_{i_r}$. These images span $W$.

For an $(r+t)$-set $T$, let $V_T$ be its coordinate subspace. The matrix restricted to $T$ has rank $t$, so $U\cap V_T$ has dimension $r$. The wedge of a basis of this intersection is a nonzero vectorEvery coefficient $c_e$ is nonzero. Indeed, projection from $U\cap V_T$ onto the $r$ coordinates in $e$ is an isomorphism: a vector in its kernel would be supported on $T\setminus e$, where the $t$ columns are independent, and hence would be zero. That projection's determinant is precisely the corresponding wedge coefficient. Thus, in the quotient vector space,For a missing edge, choose its strong-saturation witness $T$. All other vectors in this relation come from present edges, so the missing edge's vector is in their span. Consequently the present-edge vectors already span all of $W$. Their number is at least its dimension:This is sharp. Take all $r$-sets that meet a fixed $t$-set $D$. A missing edge $e$ is disjoint from $D$, and on $e\cup D$ every other $r$-set meets $D$; adding $e$ completes the required clique. The number of edges is exactly the boxed difference. If $r\le n<r+t$, no missing edge could have a witness, so a strongly saturated hypergraph must be complete; the substantive construction above is for the usual range $n\ge r+t$.

For the set-pair problem, write $m=|I|$ and choose $x_i\in R_i\cap S_i$. If $i\ne j$, the cross-disjointness implies that $x_i$ is in neither $R_j$ nor $S_j$. In particular, the witnesses are distinct. Let $D=\{x_i:i\in I\}$; each $R_i$ and $S_i$ contains exactly its own witness from $D$.

Choose two different indices $i,j$. The sets $R_i\setminus \{x_i\}$ and $S_j\setminus \{x_j\}$ are disjoint, lie outside $D$, and have sizes $r-1$ and $s-1$. HenceFor equality, partition the ground set into disjoint sets $P,Q,D$ with sizes $r-1,s-1,n-r-s+2$, respectively, and enumerate $D$ as $x_1,\dots ,x_m$. SetThen $R_i\cap S_j$ is $\{x_i\}$ for $i=j$ and empty otherwise. This realizes equality whenever the bound permits $m\ge 2$. The argument is a diagonal-intersection set-pair bound, with no additional assumptions on intersections among the $R_i$ or among the $S_i$.

The edge choices are understood to be independent, and $r$ is a fixed positive integer. We prove the hypergraph extension property and then show directly that it determines a unique countable hypergraph isomorphism type.

For a finite $S\subseteq \mathbb{N}$, prescribe a family $\mathcal{A}\subseteq \left(\genfrac{}{}{0ex}{}{S}{r-1}\right)$. We want a new vertex $v$ such thatFor any $v\notin S$, the probability of precisely this pattern in the countable random uniform hypergraph isTwo different candidate vertices use disjoint hyperedge decisions: all the other vertices in each tested edge lie in $S$. The successes are therefore independent random variables with the same positive probability $q$. The probability that the first $N$ candidates all fail is $(1-q{)}^N\to 0$. The same argument after discarding any finite initial set of candidates shows that infinitely many witnesses exist almost surely.

There are only countably many finite subsets of $\mathbb{N}$, and finitely many prescriptions for each. A countable union of null events is null. Consequently the random uniform hypergraph satisfies every such extension prescription simultaneously almost surely.

Now let $H$ and $K$ be two countably infinite $r$-uniform hypergraphs with the hypergraph extension property. Enumerate their vertex sets and construct increasing finite partial hypergraph isomorphisms by the back-and-forth method. At a forward step, take the least unused vertex $u$ of $H$. Its incident hyperedges with each $(r-1)$-subset of the current domain specify a pattern on the matched vertices of $K$. The hypergraph extension property supplies an unused vertex $v$ of $K$ with exactly this pattern. Adding $u\mapsto v$ preserves and reflects every hyperedge in the enlarged domain. At the next step, take the least unused vertex of $K$ and perform the identical construction with $H$ and $K$ interchanged.

The union of the finite maps is defined on every vertex and has every vertex in its range. It is a bijection, and each finite $r$-set appears at some finite stage, so all hyperedges and nonedges are preserved. Thus it is a hypergraph isomorphism. Existence of at least one structure with the property follows from the probability-one construction already proved; fix one representative and call it $G_{\mathrm{univ}}^{(r)}$. ThereforeThe hypergraph isomorphism type does not depend on $p$. In the case $r=2$ it is the Rado graph. For $r=1$, the argument says that the infinitely many selected and unselected singleton vertices determine the same one-uniform structure for every $p\in (0,1)$.

For a fixed uniform hypergraph $H$ with $h$ vertices, uniformity $\ell$, and at least one edge, define its Turán density bywhere $\mathrm{ex}(n,H)$ is the maximum edge count of an $H$-free hypergraph. The limit exists: averaging the edge count over all $m$-vertex subsets of an extremal $n$-vertex hypergraph, with $n\ge m\ge \ell$, shows that the displayed normalized extremal numbers are nonincreasing. Thus their limit is their infimum.

For hypergraph supersaturation by sampling, choose $m\ge h$ so that $\mathrm{ex}(m,H)/\left(\genfrac{}{}{0ex}{}{m}{\ell }\right)\le \pi (H)+ϵ/2$. The expected edge count in a uniform $m$-vertex subset of $G$ is at least $(\pi (H)+ϵ)\left(\genfrac{}{}{0ex}{}{m}{\ell }\right)$. A subset containing no copy of $H$ has at most $(\pi (H)+ϵ/2)\left(\genfrac{}{}{0ex}{}{m}{\ell }\right)$ edges, while any subset has at most $\left(\genfrac{}{}{0ex}{}{m}{\ell }\right)$. Hence at least an $ϵ/2$ fraction of the subsets contain $H$. Every particular copy of $H$ lies in exactly $\left(\genfrac{}{}{0ex}{}{n-h}{m-h}\right)$ such subsets, so their number is at leastfor $n\ge N=\max (m,2h)$. TakeFor $n<N$, the requested integer lower bound is zero; for $n\ge N$, the calculation proves it. This positive $\delta$ depends only on $H$ and $ϵ$. If the density hypothesis is impossible there is nothing to prove. For an edgeless $H$, every $h$-set is already a copy and the conclusion follows directly.

For the edge-triangle objective, let $N(v)$ be the open neighbourhood of $v$ and define its local scoreIt counts the contribution to $k_2-c{k}_3$ of edges and triangles in a graph containing $v$. If $u,v$ are nonadjacent, making $u$ a false twin of $v$ changes the objective by $s(v)-s(u)$, since no edge or triangle in a graph uses both. More generally, partition vertices into false-twin classes, meaning equal open neighbourhoods. If distinct classes $U,V$ have no edges between them, making every vertex of $U$ a twin of a representative of $V$ changes the objective by $|U|(s(v)-s(u))$. Choose the direction with nonnegative change.

Among graphs maximizing the objective, choose one maximizing the sum of squared false-twin class sizes. The operation cannot split any old false-twin class and merges $U,V$, so it would strictly increase that secondary quantity. Therefore no two distinct classes can be nonadjacent. An objective maximizer is a complete multipartite graph. This edge-triangle symmetrization works for every real $c$, with no assumption on its sign.

For positive part sizes $a_1,\dots ,a_q$, the correct multipartite formula isThe first sum in the printed intermediate formula has inconsistent indices; the edge count is the pairwise-product sum above. Fix two part sizes with sum $A$ and let $B$ be the sum of all other sizes. All terms varying with the pair have the formChoose a maximizing partition with the fewest nonempty parts. If $1-cB\le 0$, merging those two parts cannot decrease $F$ and reduces the number of parts, a contradiction. Therefore this coefficient is positive for every pair. If two integer sizes differ by at least two, moving one vertex from the larger to the smaller increases their product and hence $F$, again a contradiction. All sizes differ by at most one, so a maximizer is a Turan graph. This is balancing a multipartite edge-triangle objective.

Next maximize the same polynomial on the compact simplex of nonnegative real sizes summing to $n$, starting with at least two possible parts. Choose a maximizer with the smallest positive support. The merging argument still applies, and now varying two positive unequal sizes towards equality improves the product. Thus every positive size is $n/q$ for some integer $q$. A two-part choice has value $n^2/4>0$ when $n>0$, so $q\ge 2$. The optimum is attained at rational sizes, and thereforeOne may take the initial simplex to have $\max (n,2)$ coordinates, so it includes every multipartite graph obtained above; zero coordinates are discarded.

Set $c=9/(4n)$. Dividing the right side by $n^2$ givesbecause $q$ is an integer at least two. Rearranging provesEquality in the continuous calculation occurs at two or three equal parts, explaining the triangle support line between bipartite and tripartite Turan graphs.

A clean proof outline uses hypergraph removal rather than the quadratic density increment route. The structure is: establish removal for the three-uniform tetrahedron, encode four-term arithmetic progressions as its copies, and use the many edge-disjoint copies coming from constant progressions to contradict removal. We give the technical regularity stage in outline, as requested, and prove the counting inequality and the encoding that make the argument work.

The needed tetrahedron removal lemma says that for each $\eta >0$ there is $\rho >0$ such that a three-uniform hypergraph on $v$ vertices with fewer than $\rho v^4$ copies of $K_4^3$ can be made $K_4^3$-free by removing fewer than $\eta v^3$ hyperedges. Equivalently, being a fixed positive edge-edit distance from $K_4^3$-free forces a positive fourth-power copy count. Constants and whether copies are ordered are immaterial after rescaling $\rho$.

Here is the global proof of this hypergraph removal input. Strong regularity for three-uniform hypergraphs partitions both vertices and the bipartite pair sets between vertex classes. The resulting three-class cells, called triads in a hypergraph regularity partition, are supported on three pair cells. On all but a prescribed small total weight, the triple-edge function has approximately constant relative density and a small relative three-dimensional box norm. This two-level refinement is essential: a vertex partition alone does not capture correlations carried by pairs. The regularity construction uses the squared L2 norms of conditional expectations of edge indicators as bounded energies. Refinement increases this energy by the squared L2 norm of the difference between the new and old conditional expectations, by orthogonality. Thus a nonuniformity witness causing a definite discrepancy causes a definite energy increment. A witness to nonuniformity refines the relevant pair or triple partition and raises the appropriate energy. A hierarchy of tolerances, with sufficiently strong refinement at the pair level, makes these increases terminate after a bounded number of stages. Bounds may depend very badly on the requested tolerance, which is harmless for a qualitative theorem.

Delete hyperedges with two vertices in the same vertex class, hyperedges meeting exceptional classes or irregular cells, hyperedges supported on pair cells of very small density, and hyperedges in triads of very small triple density. Choose the cutoffs and error hierarchy so that the total deleted is less than $\eta v^3$. A surviving $K_4^3$ selects four vertex classes, six pair cells and four triads with all required densities above their cutoffs. The relative tetrahedron counting lemma gives at least $\rho v^4$ copies in those cells. This contradicts the assumed sparse copy count, and proves the tetrahedron removal lemma. The strong regularity and relative counting estimates are the technical portion outlined here; the dependence of their constants is not needed.

To show the key analytic mechanism in that counting step, define the three-dimensional box norm of a complex function on $X_1\times X_2\times X_3$ bywhere $\mathcal{C}$ denotes complex conjugation. If the other three functions are bounded by one, thenFor a proof, fix $x_0$ first. Apply the Cauchy-Schwarz inequality over $(x_2,x_3)$ to remove $g_1$, duplicating $x_1$. Next apply the Cauchy-Schwarz inequality over the variables other than $x_2$ to remove the two factors from $g_2$, duplicating $x_2$. A third application removes the four factors from $g_3$ and duplicates $x_3$. The resulting eighth power is exactly the cube average displayed above. Averaging over $x_0$ proves the inequality. This also shows nonnegativity of the cube average by its successive squared-sum form.

For example, on complete pair supports, if four triple-edge functions $f_i$ have constant parts $d_i$ and $\Vert f_i-d_i{\Vert }_{{\square }^3}\le \xi$, telescope the fourfold product and apply this inequality to each term. Their hypergraph clique density differs from $d_0{d}_1{d}_2{d}_3$ by at most $4\xi$, so it is positive when $4\xi <{\prod }_i{d}_i$. On general pair supports the same successive squaring argument is combined with sufficiently regular pair cells; choosing relative errors small compared with the pair-density product gives the relative tetrahedron counting lemma. This explains both the counting step and why its support must be regularized before the triple-edge densities. It supplies a proved important step without pretending that the strong regularity theorem is a one-line assertion.

We now prove the four-term progression hypergraph encoding completely. Let $A\subseteq [N]$ have subset density at least $\delta >0$, choose $M=4N+1$, and take four disjoint copies $X_0,\dots ,X_3$ of the cyclic group $G=\mathbb{Z}/M\mathbb{Z}$. Put a hyperedge on the three vertices excluding part $i$ precisely whenFor a transversal quadruple let $S_0={\sum }_j{x}_j$ and $S_1={\sum }_{j}j{x}_j$. Its four edge conditions are $S_1-i{S}_0\in A$, $i=0,1,2,3$. Thus a $K_4^3$ gives a four-term arithmetic progression with common difference $-S_0$ modulo $M$.

Suppose $A$ has no nonconstant four-term arithmetic progression in the integers. A modular progression lying in $[N]$ must also be an integer progression: each consecutive second difference has absolute value less than $2N<M$, so its congruence to zero is an equality. Therefore every $K_4^3$ in this hypergraph has $S_0=0$, and all four values equal some $a\in A$. For each $a$, the system $S_0=0$, $S_1=a$ has exactly $M^2$ solutions: choose $x_2,x_3$, solve first for $x_1=a-2x_2-3x_3$, and then for $x_0=-x_1-x_2-x_3$. There are exactly $|A|M^2=O(M^3)$ copies of $K_4^3$.

These copies are edge-disjoint. Indeed, an edge missing part $i$ has exactly one completion with $S_0=0$, obtained by setting $x_i=-{\sum }_{j\ne i}{x}_j$. Its common value is the already prescribed $L_i\in A$. Hence destroying all copies requires at least $|A|M^2$ edge deletions. Since $M\le 5N$, this is at least $\delta M^3/5$. Apply the tetrahedron removal lemma to the $v=4M$ vertices with, for instance, $\eta =\delta /640$. It would permit fewer than $\delta M^3/10$ deletions once $M$ is large: the copy count $O(M^3)$ is eventually below its fixed threshold $\rho (4M{)}^4$. This is impossible.

Every fixed positive density therefore forces a nonconstant four-term arithmetic progression in sufficiently long intervals. This proves the length-four case of the Szemerédi theorem. Applying it to sufficiently large initial intervals along a subsequence witnessing positive upper asymptotic density also gives the usual infinite-set formulation.

Assume the uniform hypergraph has positive average hypergraph vertex degree $d$, so $nd=re(G)$. Its hypergraph degree measure isIt is a probability measure on the vertex set; vertices of degree zero have measure zero. If the hypergraph is regular, it equals $|S|/n$. An edgeless hypergraph has no normalized degree measure of this form and must be treated separately.

Every edge entirely in $S$ contributes $r$ to the degree sum over $S$, giving the upper bound. For the lower bound, an edge entirely in $S$ contributes $r$, and any other edge contributes at most $r-1$. ThereforeTogether these give both degree-measure inequalities:In particular every hypergraph independent set has measure at most $1-1/r$, which explains why degree measure can control containers even in very nonregular hypergraphs.

A sufficient container theorem. For every fixed $r\ge 2$, there are positive constants ${\delta }_r,{\tau }_r,c_r,K_r$ such that if $0<\tau \le {\tau }_r$ andthere is a family of hypergraph containers covering all hypergraph independent sets, each with $\mu (C)\le 1-c_r$. Each container is determined by a container fingerprint $T$ with $|T|\le K_r\tau n$ and $\mu (T)\le K_r\tau$. In particular, for sufficiently small $\tau$, the number of containers is at most $\exp (O_r(\tau n\log (1/\tau )))$. We will give an algorithm and constants establishing this version.

The golden rule for container algorithms is that reconstruction may depend on the small container fingerprint, but never on unrevealed information about the independent set. When a deterministic test calls for inspecting a vertex, a positive membership answer is recorded in the container fingerprint, while a negative answer permits its exclusion from the container. All tests and all state updates must be reproducible using that container fingerprint. Choosing tests that permit only a few positive answers then yields few containers.

Here is an explicit implementation with controlled links. Use the fixed order $1,\dots ,n$, parameters $\tau ,\delta ,\zeta >0$, and a bound $d_G(\sigma )\le \delta d{\tau }^{|\sigma |-1}$ on nonsingleton codegrees. Let $d_s(\sigma )$ count incidences with multiplicity in the $s$-uniform multihypergraph $P_s$. Define thresholdsA saturated subset is one whose current degree has reached its threshold.

Every generated edge of $P_s$ extends to an original edge by adding $r-s$ earlier vertices from $T$. Thus, for a hypergraph independent set $I$, no singleton generated in $P_1$ can be a member of $I$. In particular an inspected vertex in ${\Gamma }_1$ cannot give a positive membership answer. All other positive answers are recorded. The golden rule for container algorithms now proves that the reconstructed container contains $I$ and that its state depends only on $T$.

Control the possible overshoot at saturation. The multisets are added in batches; merely claiming $d_s(\sigma )\le {\theta }_s(\sigma )$ would be wrong. In the last batch that increases $d_s(\sigma )$, the set $\sigma$ was not yet saturated, and the batch comes from some vertex $v\notin \sigma$. Its contribution is at most $d_{s+1}(\sigma \cup \{v\})$. HenceInduction downwards from $P_r$ yields, for $|\sigma |\ge 2$,Indeed the two terms in the last-batch bound have coefficients $1$ and $r-s$ with the same power of $\tau$. Applying this nonsingleton bound to $\{u,v\}$ gives the singleton estimateSumming over $U$, using $|U|\le n$, proves the requested estimate at every stage of the algorithm:It applies with multiplicities; replacing the multisets by sets in the accounting would invalidate the argument.

Check that the container fingerprint is small and the container loses positive measure. Assign each positive inspected vertex to one index $s$ witnessing its test. Its added link batch has size at least $\zeta {\tau }^{r-s-1}{d}_G(v)$. Distinct batches count separately in the multiset. Since $|P_s|=s^{-1}{\sum }_u{d}_s(u)$, the preceding bound givesThe second inequality uses $d_G(v)\ge \zeta d$ for every $v\in T$.

For completeness, the loss of measure can be verified by a short incidence count. Put $D=([n]\setminus C)\cup T\cup B$ and $a_s=|P_s|/({\tau }^{r-s}nd)$. Every saturated singleton belongs to $D$. Partition $P_{s+1}$ by its earliest vertex. An earliest vertex in $D$ accounts for at most ${\tau }^{r-s-1}nd(\mu (D)+r\delta )$ incidences. For any other earliest vertex, the unsaturated link has size less than $\zeta {\tau }^{r-s-1}{d}_G(v)$; the remaining edges meet some saturated subset of ${\Gamma }_s$.

For a saturated nonsingleton $\sigma$, the degree bounds imply $d_{s+1}(\sigma )\le (r/\tau )d_s(\sigma )$. For a saturated singleton the corresponding bound is $d_{s+1}(u)\le {\tau }^{-1}{d}_s(u)+r\delta d{\tau }^{r-s-1}$. Every multiedge of $P_s$ has fewer than $2^s$ nonempty subsets. These observations giveFor $s=1$, all saturated subsets are singletons in $D$, so directly summing their $P_2$ degrees givesSince $a_r=1/r$, these inequalities prevent $D$ from having arbitrarily small measure. To make the constants explicit, letIterating the displayed inequalities gives $a_r\le L(\mu (D)+\zeta +3r\delta )$, hence $\mu (D)\ge 3b/4$ whenever $\delta \le {\delta }_r$. Also $r\delta \le 1$, so $\tau \le {\tau }_r$ gives $\mu (T)\le 2r\tau /\zeta \le b/8$, while $\mu (B)\le \zeta =b/8$. ThereforeOne can take $K_r=2r/{\zeta }^2$ in the stated container fingerprint bounds. Counting subsets of size at most $K_r\tau n$ gives the asserted bound on the number of containers. Thus the explicit algorithm produces the family promised by the sufficient hypergraph container theorem, as well as the required intermediate degree estimate.

For the standard weak-threshold formulation, see Online containers for hypergraphs. The constants above come from the explicit incidence estimates given here.

For $r=1$, no multilevel construction is needed: take the sole container to be the vertices that are not singleton edges. It contains every hypergraph independent set and has degree measure zero when $d>0$; its fingerprint is empty. The requested degree-sum inequality follows directly from the definition of $\mu$.

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.