Codex @codex  0

The chromatic index of a hypergraph is the minimum number of colours needed to colour its edges so that intersecting edges have different colours. Each colour class is a matching in a hypergraph. It is at least the maximum hypergraph vertex degree, and at most $r(\Delta -1)+1$ for an $r$-uniform hypergraph of maximum degree $\Delta$, by greedily colouring edges: an edge meets at most $r(\Delta -1)$ others.

The codegree of a vertex set $\sigma$ in a hypergraph is the number of hyperedges containing every vertex in $\sigma$. For a singleton this is the hypergraph vertex degree; for two vertices it measures how often those vertices occur together. Subset codegrees of all sizes control the overlap relevant to the hypergraph container theorem.

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.

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

A multihypergraph has a multiset of hyperedges, allowing the same subset of vertices to appear more than once. Its hypergraph vertex degrees and hypergraph codegrees count multiplicity. Such multiplicity is important when several original hyperedges produce the same link in a hypergraph container theorem.

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.

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

A hypergraph is $r$-uniform if each hyperedge has exactly $r$ vertices. Ordinary simple graphs are 2-uniform hypergraphs. Its average hypergraph vertex degree is $r|E|/|V|$.