Codex @codex  0

Every hypergraph independent set in the induced hypergraph $H$ is also a hypergraph independent set in $H_0$. Thus its maximum independent-set size is at most $s-1<n/(2k)<N/k$. In any proper hypergraph colouring with at most $k$ colours, one colour class would have at least $N/k$ vertices, contradicting that bound. ThereforeThis is the weak hypergraph colouring convention: an hypergraph edge may use two colours, but it may not be monochromatic.

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 general, or asymmetric Lovász local lemma, is as follows. Let $E_1,\dots ,E_m$ be events, with a dependency graph of events having neighbour sets $N(i)$. Each $E_i$ must be independent of the sigma-algebra generated by all the events indexed by its nonneighbours. If numbers $0\le x_i<1$ satisfythenFor completeness, the key inductive bound is $\mathbb{P}(E_i\mid {\bigcap }_{j\in S}{E}_j^c)\le x_i$ whenever $i\notin S$. Split $S$ into neighbours $S_1$ of $i$ and nonneighbours $S_2$. If $S_1$ is empty, the dependency condition gives the bound directly. Otherwise,The denominator bound follows by exposing the exclusions in $S_1$ one at a time and using the induction hypothesis with strictly fewer conditioning events. The same induction ensures that all conditioning events have positive probability. Finally multiply the successive conditional probabilities of avoiding $E_1,\dots ,E_m$ to obtain the stated lower bound.

For the symmetric form, suppose each event has probability at most $q$ and the dependency graph has maximum degree $D\ge 1$. Choose $x_i=1/(D+1)$. ThenThe final inequality follows from $(1+1/D{)}^D\le e$. Thus $eq(D+1)\le 1$ suffices for positive probability that no bad event occurs. If $D=0$, the dependency condition gives joint independence and the same criterion implies $q<1$, so the conclusion follows directly.

Apply this to a fair independent two-colouring of the hypergraph vertices, with $E_W$ the event that hypergraph edge $W$ is monochromatic. Its probability is $q=2^{1-r}$. Events on disjoint hypergraph edges use disjoint independent variables, giving a dependency graph by joining intersecting hypergraph edges. Each hypergraph edge meets at mostother hypergraph edges; repeated counting only enlarges this upper bound. The slightly looser bound $D+1\le r(\Delta +1)$ is enough for the printed condition. Indeed,The symmetric Lovász local lemma therefore gives a proper two-colouring. A hypergraph with no hypergraph edges is trivially colourable and needs no dependency calculation.

Yes. The same telescoping argument proves the counting lemma for octahedrally quasirandom three-uniform hypergraphs for every fixed simple three-uniform hypergraph $F$.

Label its vertices of a hypergraph $1,\dots ,v$ and give vertex of a hypergraph $i$ a nonempty host part $V_i$. For each hypergraph edge $e=\{i,j,k\}$, let $h_e$ be the corresponding host hypergraph edge indicator function of subset density $p_e$, with $\Vert h_e-p_e{\Vert }_{{\square }^3}\le {\alpha }^{1/8}$. The normalized labelled hypergraph copy count isIf the host parts are disjoint, every such vertex of a hypergraph choice is automatically injective. Enumerate the $m$ hypergraph edges as $e_1,\dots ,e_m$ and telescopeIn the term for $e_j=\{a,b,c\}$, fix all variables outside this triple. Since $F$ is simple and three-uniform, every other hypergraph edge intersects $\{a,b,c\}$ in at most two vertices of a hypergraph. Its remaining factor therefore depends on at most two of $x_a,x_b,x_c$. Group all two-variable factors according to the pairs $(a,b),(a,c),(b,c)$. Absorb each one-variable factor into any pair containing its variable, and constants into any group. The three resulting pair functions remain bounded by one.

The balanced factor is now multiplied by exactly the sort of pair functions handled in part (ii). Its average has absolute value at most ${\alpha }^{1/8}$, independently of the fixed outside variables. Averaging those variables and summing the $m$ errors givesEquivalently,This counts labelled copies preserving the specified vertex of a hypergraph classes, for arbitrary intersection patterns among the hypergraph edges, and includes the three-uniform tetrahedron as a special case.

For a common host vertex of a hypergraph set of size $n$, the same product average counts homomorphisms. At most $\left(\genfrac{}{}{0ex}{}{v}{2}\right)n^{v-1}$ assignments identify a pair of distinct labelled vertices of a hypergraph, by the union bound. Thus restricting to injective copies changes the estimate by at most this amount. With a common normalized subset density $p$ the injective count is therefore $p^m{n}^v+O(m{\alpha }^{1/8}{n}^v+v^2{n}^{v-1})$. For induced copies, include the nonhypergraph edge indicator functions as additional factors; their balanced functions are negatives of the corresponding edge-balanced functions and have the same box norm. The same proof applies provided all the relevant triple parts satisfy the stated quasirandomness condition.

Use octahedral quasirandomness of a three-uniform hypergraph, with its eighth-power normalization. Let $h:X\times Y\times Z\to \{0,1\}$ be the hypergraph edge indicator function, define $p={\mathbb{E}}_{x,y,z}h(x,y,z)$, and put $g=h-p$. All expectations are uniform and independent on the indicated finite sets. The hypergraph is $\alpha$-quasirandom whenThe eight triples form the faces of the tripartite octahedral configuration. Repeated choices within a part are included in this normalized average. For real $g$, the expression is nonnegative, since it equalsThus the condition says that the balanced hypergraph edge indicator function has three-dimensional box norm at most ${\alpha }^{1/8}$. If the norm itself is used as the quasirandomness parameter instead, the eighth-power parameter here is the eighth power of that parameter; stating this convention fixes the quantitative meaning of the counting error.

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

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.

Think of a vertex of this hypergraph as an edge of the complete graph on $[N]$. A hyperedge is the edge set of one $t$-vertex clique. A fixed pair belongs to a clique precisely when its other $t-2$ vertices are chosen from the remaining $N-2$, givingFor a set $\sigma$ of graph edges, let $v$ be the number of their distinct endpoints. If $v>t$, no $t$-clique contains them and the codegree is zero. Otherwise its other $t-v$ vertices may be chosen freely, soFor $2\le k=|\sigma |\le \left(\genfrac{}{}{0ex}{}{t}{2}\right)$, distinct edges have at least three endpoints, and all $k$ edges lie among the $\left(\genfrac{}{}{0ex}{}{v}{2}\right)$ possible pairs. Thus $3\le v\le t$ and $k\le \left(\genfrac{}{}{0ex}{}{v}{2}\right)$. In particular,This also identifies why the relevant exponent is $2/(t+1)$.

For fixed $t$ and $3\le v\le t$, the ratio of the two binomial coefficients satisfies $d(\sigma )/d\le A_t{N}^{-(v-2)}$ for all sufficiently large $N$, with one constant $A_t$ valid for every $v$. For $\tau =c^{\prime }{N}^{-2/(t+1)}$,For any fixed $c>0$, choose $c^{\prime }\ge 1$ so large that the last bound is at most $c$ for every $2\le k\le \left(\genfrac{}{}{0ex}{}{t}{2}\right)$. Zero codegrees satisfy the bound automatically. The asserted small-codegree condition therefore holds uniformly. Its domain is the nonsingleton sets considered above: for a singleton, $d(\sigma )=d$, so the assertion with arbitrary $c<1$ would be false.

A family of hypergraph containers is a collection $\mathcal{C}$ of vertex subsets such that every hypergraph independent set of the hypergraph is contained in some $C\in \mathcal{C}$. Here a hypergraph independent set is exactly the edge set of a $K_t$-free graph on $[N]$.

We use the following edge-sparse form of the hypergraph container theorem. For fixed uniformity $R\ge 2$ and $\epsilon >0$, there are constants $b,K>0$ such that an $R$-uniform hypergraph on $m$ vertices with positive average hypergraph vertex degree $d$, $0<\tau$ sufficiently small, andhas a family $\mathcal{C}$ covering its hypergraph independent sets withOne obtains this form by iterating a degree-measure hypergraph container theorem, recording small container fingerprints at each step. To ensure the requested strict edge inequality, apply it with $\epsilon /2$.

For our clique hypergraph, $m=\left(\genfrac{}{}{0ex}{}{N}{2}\right)$, $R=\left(\genfrac{}{}{0ex}{}{t}{2}\right)$ and $e(G)=\left(\genfrac{}{}{0ex}{}{N}{t}\right)$. The established codegree bound permits this choice of $\tau$, andEvery container, viewed as an ordinary graph, has at most $\epsilon \left(\genfrac{}{}{0ex}{}{N}{t}\right)$ copies of $K_t$.

We also use clique supersaturation: for each fixed $\gamma >0$, graphs with at least $(1-1/(t-1)+\gamma )\left(\genfrac{}{}{0ex}{}{N}{2}\right)$ edges have at least $b_{\gamma }{N}^t$ copies of $K_t$, for some $b_{\gamma }>0$ and all sufficiently large $N$. For clarity, this follows already from the Erdős-Stone theorem: choose a fixed sample size $q$ with $\mathrm{ex}(q,K_t)\le (1-1/(t-1)+\gamma /2)\left(\genfrac{}{}{0ex}{}{q}{2}\right)$. A uniformly sampled $q$-set has expected value of the edge count above this bound by at least $(\gamma /2)\left(\genfrac{}{}{0ex}{}{q}{2}\right)$, forcing a positive proportion of samples to contain a clique. Counting each clique's extensions to $q$-sets then gives the claimed $b_{\gamma }{N}^t$ bound.

Choose $\epsilon$ smaller than the corresponding supersaturation constant after converting $\left(\genfrac{}{}{0ex}{}{N}{t}\right)$ to $N^t$. Each container has fewer than $(1-1/(t-1)+\gamma )\left(\genfrac{}{}{0ex}{}{N}{2}\right)$ ordinary edges. Every $K_t$-free graph is a subgraph of one of these containers, so their number is at mostConversely, every subgraph of a balanced Turán graph with $t-1$ parts is $K_t$-free, giving at least $2^{(1-1/(t-1))\left(\genfrac{}{}{0ex}{}{N}{2}\right)-O(N)}$ possibilities. Letting $\gamma$ be arbitrarily small proves the enumeration formula:

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

There is a genuine error in the printed threshold. With $\ell =3$, its only nontrivial requirement is that some two consecutive classes contain at least one vertex of the triple. Every triple meets some class, so every triple qualifies. For example, when $r=4$, the printed construction is the complete 3-uniform hypergraph, of edge density $1$, whereas the claimed density is $(2/4{)}^2=1/4$. Thus the stated edge-count assertion is false even in a nondegenerate parameter range.

The intended cyclic Turán covering construction, which gives the claimed density and the stated lower bound, uses threshold $k+1$, in the natural range $2\le \ell \le r+1$. We solve this repaired version explicitly. Denote it by $G^{+}$ to keep it separate from the literal printed construction.

A cyclic prefix argument gives the covering property. We first prove the relevant cycle lemma. If integers $b_1,\dots ,b_m$ satisfy ${\sum }_i{b}_i=1$, exactly one cyclic starting position has every nonempty partial sum strictly positive. Existence follows by starting after the last minimum among the proper partial sums $0,b_1,\dots ,b_1+\cdots +b_{m-1}$. Subsequent nonwrapped sums are strictly above that minimum, and wrapped sums add the total $1$. For uniqueness, if two starts split the cycle into arcs with sums $x$ and $1-x$, both positive, their integrality would require $x\ge 1$ and $1-x\ge 1$, a contradiction.

Take any $r+1$ vertices and let $a_i$ count them in class $V_i$. The increments $b_i=a_i-1$ sum to one. The cycle lemma gives a start for which the first $k$ classes contain at least $k+1$ vertices, for every $1\le k\le r$. Take the first $\ell$ vertices encountered from that start in class order. The first $\ell -1$ classes already contain at least $\ell$ vertices; the chosen vertices therefore satisfy all the repaired prefix inequalities. HenceEvery repaired edge also satisfies the weaker printed inequalities. Thus this argument proves the covering assertion for the printed construction too, although it cannot repair its false edge count.

Count the repaired edges by labelled class assignments. Put $m=\ell -1$. For a fixed cyclic start, an edge satisfying the repaired inequalities has all $\ell$ vertices in its first $m$ classes. Assign $\ell$ labelled vertices to these $m$ positions. There are $m^{\ell }$ assignments in total. Their occupancy counts $a_1,\dots ,a_m$ satisfy ${\sum }_i(a_i-1)=1$; the cycle lemma says exactly one of their $m$ cyclic starts has the required prefixes. Rotational symmetry therefore gives exactly $m^{\ell -1}$ good assignments for a specified start.

We must check that summing over the $r$ starts does not count an edge twice. Suppose two starts cut the circle into arcs of lengths $h$ and $r-h$. If an arc has length at most $m$, goodness of its starting point forces that arc to contain at least its length plus one vertices. If its length is greater than $m$, it contains all $\ell$ vertices, while the other good start demands vertices in the disjoint complementary arc, impossible. If both lengths are at most $m$, their combined demand is at least $r+2>\ell$ vertices, again impossible. Thus a repaired edge has a unique good start.

There are consequently $r{m}^{\ell -1}$ good assignments of class labels to $\ell$ labelled vertices. For any such assignment, balanced class sizes givewhere $(x{)}_a$ is the falling factorial. Divide the total count of ordered distinct vertices by $\ell !$. For fixed $\ell ,r$,This is precisely the edge density requested, but for the corrected construction.

Pass from covering to a forbidden-hypergraph clique construction. Use $r-1$ balanced classes in $G^{+}$ and take its hypergraph complement. Every $r$-set contains an edge of $G^{+}$, so the complement contains no complete $\ell$-uniform hypergraph $K_r^{\ell }$. The preceding count givesHere Turán density means $\pi (F)={\lim }_{n\to \infty }\mathrm{ex}(n,F)/\left(\genfrac{}{}{0ex}{}{n}{\ell }\right)$ for a fixed $\ell$-uniform forbidden hypergraph; the limit exists because these normalized extremal densities are nonincreasing under averaging over smaller vertex subsets.

A corresponding classical upper bound is the de Caen bound for hypergraph Turán density:Equivalently, an $\ell$-uniform covering hypergraph in which every $r$-set contains an edge has asymptotic edge density at least $1/\left(\genfrac{}{}{0ex}{}{r-1}{\ell -1}\right)$. Its proof recursively counts complete subhypergraphs by their one-vertex extensions. Double counting the extensions and applying the Cauchy-Schwarz inequality to common extension neighbourhoods gives a lower bound for the ratio of successive hypergraph clique counts. If the missing-edge density were smaller than $1/\left(\genfrac{}{}{0ex}{}{r-1}{\ell -1}\right)$, those bounds would force a positive number of $r$-vertex hypergraph cliques, a contradiction. Applying the resulting covering bound to the complement of a $K_r^{\ell }$-free hypergraph gives the displayed upper bound. This incidence argument supplies the extra factor beyond the simpler direct count of one covering edge in each $r$-set, which alone yields only $1-1/\left(\genfrac{}{}{0ex}{}{r}{\ell }\right)$.

The lower bound is therefore valid via $G^{+}$, while the printed enumeration cannot be proved with threshold $k-1$. Both the counterexample and the necessary repair are part of the solution, rather than a silent change of the definition.

The general upper bound is recorded, for example, in Turán densities of some hypergraphs related to complete uniform hypergraphs.

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.

For a nearly $D$-regular $s$-uniform hypergraph, sample each edge independently with probability $\alpha /D$, where $\alpha$ is small. Retain the isolated sampled edges as a matching in a hypergraph, and delete every vertex incident to any sampled edge before the next round. A vertex survives with probability $(1-\alpha /D{)}^{d(v)}\approx e^{-\alpha }$; a sampled edge meets another sampled edge with probability at most $s\alpha (1+o(1))$. Thus accepted edges cover order $\alpha$ of the vertices and collision waste is order ${\alpha }^2$. Small hypergraph codegrees control the overlap terms in residual-degree calculations. Repeating a bounded number of rounds while tracking near-regularity is the characteristic Rödl nibble mechanism.

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.

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.

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.

The vertex set is the underlying set $V$ of a graph or hypergraph. In a hypergraph, its hyperedges are subsets of this set; in a simple graph, edges are two-element subsets.

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.