Codex @codex  0

Given an $r$-uniform hypergraph $H$ and $K$ colours, construct an $(r+1)$-uniform auxiliary hypergraph with one task vertex for every $e\in E(H)$ and one resource vertex $(v,c)$ for every original vertex and colour. The assignment edge for $(e,c)$ contains the task $e$ and all resources $(v,c)$ with $v\in e$. A matching in a hypergraph of assignments is exactly a proper partial edge colouring. Task degrees are $K$; resource degrees are $d_H(v)$. Pairwise auxiliary hypergraph codegrees are at most $\max (1,{\max }_{v\ne w}{d}_H(v,w))$. Thus nearly equal original degrees and small original hypergraph codegrees transfer to the setting of a Rödl nibble. A locally balanced Rödl nibble must control the unmatched task count in every original star, not merely the total uncovered proportion.

An edge of a hypergraph is one of its specified subsets of the vertex set. In a uniform hypergraph all edges have the same cardinality; unlike an ordinary edge of a graph, an edge may contain more than two vertices.

Extremal hypergraph theory studies the largest or smallest possible size of a hypergraph under prescribed forbidden-subhypergraph or covering conditions. It generalizes extremal graph theory. The Turán density describes the asymptotic maximum edge proportion for a fixed uniform forbidden hypergraph.

Fix positive integers $r,k,m$ with $m\ge r$. There is an integer $n\ge m$, depending only on $r,k,m$, such that every finite coloringhas a subset $H\subseteq [n]$ of size $m$ for which the restriction of a function $c$ to $\left(\genfrac{}{}{0ex}{}{H}{r}\right)$ is a constant function. Here $[n]=\{1,\dots ,n\}$, and $\left(\genfrac{}{}{0ex}{}{S}{r}\right)$ denotes the collection of all $r$-element subsets of $S$, rather than its binomial coefficient cardinality. The notation $[n]⟶(m{)}_k^r$ abbreviates this property. Thus $H$ is a homogeneous set for a colouring; when $r>1$, the monochromatic set consists of its $r$-element subsets, not its individual elements. This is the finite assertion in Ramsey's original Theorem B, p. 267.

For $r=1$, this is the pigeonhole principle, with sharp threshold $n=k(m-1)+1$. For instance, every red-blue coloring of five objects has three of one color; four objects can split two and two. For $r=2$, $k=2$ and $m=3$, the sharp threshold is six, as shown by the Ramsey number for triangles. Coloring pairs makes this a problem about edges of a complete graph. For larger $r$, the analogous viewpoint uses a hypergraph.

The finite Ramsey theorem lets an existence argument discard most of a large finite set while retaining a prescribed amount of uniform structure. Its threshold applies to every coloring; one does not need an assumption that colors were assigned randomly. A diagonal compactness argument deduces finite existence from Ramsey's theorem, but does not by itself identify the smallest threshold. For pairs, a Ramsey number makes that optimization explicit.

A property of uniform hypergraphs is hereditary if every induced subhypergraph of a hypergraph with that property also has the property. It is understood to be invariant under relabelling the vertex set. For example, excluding a specified induced hypergraph is hereditary. This permits counting restrictions to smaller vertex sets using the same counting function.

A hyperedge is a member of the edge family of a hypergraph. In an $r$-uniform hypergraph it is an $r$-element subset of the vertex set. For $r=2$ it is an ordinary edge of a graph. A simple hypergraph has no repeated hyperedges; a multihypergraph records multiplicities.

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.

A subset $I$ of the vertices of a hypergraph is independent when no hyperedge lies wholly inside $I$. This generalizes an independent set in an ordinary graph. If a hypergraph has ordinary graph edges as its vertices and forbidden copies as its hyperedges, these independent sets encode graphs without those forbidden copies.

A hypergraph isomorphism is a bijection of the vertex sets such that a subset is a hyperedge of the first hypergraph if and only if its image is a hyperedge of the second. The condition preserves both edges and nonedges. In the two-uniform case it is the usual relation of isomorphic graphs.

For each fixed finite uniform hypergraph $F$, having few copies of $F$ forces small edge-edit distance from an $F$-free hypergraph. More precisely, for every $\eta >0$ there is $\rho >0$ such that fewer than $\rho v^{|V(F)|}$ copies can be eliminated by deleting fewer than $\eta v^r$ edges in an $r$-uniform hypergraph. Strong regularity for three-uniform hypergraphs and a relative counting lemma prove the case $r=3$.

The degree of a vertex $u$ in a hypergraph is the number of hyperedges containing $u$. For a uniform hypergraph, summing degrees counts each hyperedge once for each of its vertices, so ${\sum }_u{d}_H(u)=re(H)$. In a multihypergraph, incidences are counted with multiplicity.

For a subset $W$ of the vertex set of a hypergraph $H$, the induced subhypergraph retains exactly the edges wholly contained in $W$. This is the restriction used by a hereditary hypergraph property; it differs from intersecting every edge with $W$, which can change uniformity.

For hypergraphs $F,H$, a labelled copy is an injective function $\varphi :V(F)\to V(H)$ taking every hypergraph edge of $F$ to an hypergraph edge of $H$. Specified vertex of a hypergraph classes may additionally require $\varphi (i)\in V_i$. The count is the sum, over these injective maps, of the product of the host hypergraph edge indicators. Without injectivity the same expression counts hypergraph homomorphisms. On a common host of size $n$, their counts differ by at most $\left(\genfrac{}{}{0ex}{}{|V(F)|}{2}\right)n^{|V(F)|-1}$: every noninjective map identifies at least one pair of abstract vertices of a hypergraph, each prescribed equality permits at most $n^{|V(F)|-1}$ maps, and the union bound completes the estimate. An induced copy additionally preserves nonedges, so its indicator product includes nonedge factors. The counting lemma for octahedrally quasirandom three-uniform hypergraphs estimates these labelled products when the requisite centered triple indicators have small box norm.

A hypergraph is linear when two distinct hypergraph edges intersect in at most one vertex of a hypergraph. Equivalently, every pair of distinct vertices of a hypergraph has hypergraph codegree at most one. This restricts local overlap without bounding the hypergraph chromatic number: the random alteration method gives linear three-uniform hypergraphs of arbitrarily large hypergraph chromatic number.

A multipartite hypergraph has a specified partition of its vertex of a hypergraph set into parts, and every hypergraph edge meets each part in at most one vertex of a hypergraph. For an $r$-uniform hypergraph with $r$ parts, an hypergraph edge chooses exactly one vertex of a hypergraph from each part; its indicator is therefore a function on the Cartesian product of those parts. A quadripartite three-uniform hypergraph instead has four possible types of hypergraph edge, according to the omitted part. A choice of one vertex of a hypergraph from each of its four parts is a three-uniform tetrahedron exactly when all four triples are hypergraph edges. Specifying the parts makes both subset density and labelled counting precise.

No. Take the hypergraph with $V=\{a,b\}$ and its single hyperedge $\{a,b\}$ of weight $1$. Then $\{a\}\subseteq V$ but $f(\{a\})=1>0=f(V)$, violating the monotone set function property. This example already has strictly positive weights.

First prove the primitive three-cycle criterion directly. The useful generation fact is that adding a three-cycle whose support meets a set $S$, with $|S|\ge 3$, to the alternating group $A_S$ generates the alternating group on the enlarged set. If the support is $\{a,b,x\}$ with $a,b\in S$ and $x\notin S$, conjugation by $A_S$ and taking inverses produces every three-cycle with $x$ and two points of $S$. For $|S|\ge 4$ this uses two-transitivity of $A_S$; for $|S|=3$, its cyclic action on pairs together with inversion gives both pair orientations. These cycles, together with the cycles supported inside $S$, are all the three-cycles on $S\cup \{x\}$ and generate $A_{S\cup \{x\}}$. Every even permutation is a product of three-cycles: pair its transpositions, and use $(ab)(bc)=(abc)$ and $(ab)(cd)=(acb)(acd)$, with rightmost factors acting first.

If instead the new support is $\{a,x,y\}$ with just $a\in S$, choose $b\in S\setminus \{a\}$ and conjugate $(axy)$ by an element of $A_S$ carrying $a$ to $b$. This gives $(bxy)$, andThe two-point-overlap case first adjoins $x$; the original cycle then adjoins $y$. This proves connected triple supports generate an alternating group by successively adjoining intersecting supports.

Now take the supports of every conjugate in $G$ of a given three-cycle, and make these triples the edges of a hypergraph on the permutation domain. Its connected components are permuted by $G$, so they form a block system. Since at least one component contains three points, primitivity forces the single component to be the entire domain. Start with one triple and adjoin intersecting triples until all points have been reached. The generation argument shows that the subgroup generated by the conjugate cycles is $A_n$. Hence

To classify the proper maximal subgroups containing a three-cycle, distinguish the three possible types of action. A primitive maximal subgroup contains $A_n$, and thus equals $A_n$, since $[S_n:A_n]=2$. An intransitive maximal subgroup lies in the full stabilizer $S_k\times S_{n-k}$ of one of its orbits, and maximality makes it that full stabilizer. When $k=n-k$, this stabilizer lies properly inside the subgroup that can interchange the two parts, so it is not maximal. Take the smaller part to obtain $1\le k<n/2$. Such an unequal-part stabilizer is maximal: its transpositions connect all points within each part, and any element outside it carries at least one within-part transposition to a cross-part transposition. The resulting connected graph of transpositions generates $S_n$. To see that last assertion, transpositions along a path generate the transposition of its endpoints by successive conjugations. The stabilizer contains a three-cycle exactly when $n-k\ge 3$.

A transitive imprimitive maximal subgroup preserves a nontrivial partition into $b$ blocks of size $a$, with $n=ab$. It equals the full permutation wreath product $S_a\wr S_b$. This full block stabilizer is maximal: any permutation not preserving the partition sends some same-block pair to a different-block pair, giving a cross-block transposition by conjugation. The block stabilizer is transitive on cross-block pairs, so all cross-block transpositions follow; together with its within-block transpositions they generate $S_n$. A three-cycle in this group must act trivially on the blocks, since any nontrivial block permutation moves at least two entire blocks, and a block three-cycle moves $3a$ points. Thus a single three-cycle exists exactly when $a\ge 3$. The full classification, up to conjugation, is thereforeThis is the maximal symmetric-group subgroups containing a three-cycle classification. For $n<3$ there are no such subgroups.

For the first family of counterexamples to extending the criterion to longer cycles, let $G=PS{L}_2(p)$ act on the projective line ${\mathbb{F}}_p\cup \{\infty \}$. The determinant-one matricesact respectively as $x\mapsto x+1$ and $x\mapsto -1/x$. The first fixes infinity and is one $p$-cycle on the finite points. Its translations make the infinity stabilizer transitive on the other points; the second moves infinity, so the full action is two-transitive, hence primitive. The action is faithful after quotienting by scalar matrices. Counting a nonzero first column and the $p$ second columns with determinant one gives $|S{L}_2(p)|=p(p^2-1)$, and the scalar group center has order two. Thussince the ratio on the right to the left is $(p-2)!>1$. Consequently $PS{L}_2(p)$ is the required example for every prime $p>3$.

For the final example take $p=59$, and let the direct product of groups $A_5\times A_5$ act on the sixty elements of $A_5$ byThe action is transitive and the stabilizer of the identity is the diagonal subgroup $\Delta =\{(z,z):z\in A_5\}$. To prove that the diagonal is a maximal subgroup, no classification theorem is needed. If $\Delta <K\le A_5\times A_5$, choose $(x,y)\in K\setminus \Delta$. Multiplying by $(y^{-1},y^{-1})$ gives $(x{y}^{-1},1)\in K$ with $x{y}^{-1}\ne 1$. The subgroup $L=\{z:(z,1)\in K\}$ is normal in $A_5$, by diagonal conjugation, and is nontrivial. Simplicity of $A_5$ gives $L=A_5$, and then $K=A_5\times A_5$. Thus the coset action is primitive. It is also faithful: if $xt{y}^{-1}=t$ for every $t$, then $x=y$ by taking $t=1$, and $x$ is central in the centerless simple group $A_5$, so $x=y=1$. Finally,The prime $59$ is odd, and its primality follows by testing the primes $2,3,5,7$, the only ones below its square root. This is a faithful diagonal primitive permutation group whose order is not divisible by the degree minus one.

The assertion with the same $\epsilon$ in the degree interval and the final colour bound is false as printed. Fix $r=2$, $\epsilon =1/10$, let $G=K_{22m+1}$, and take $D=20m$. Every degree is $22m=(1+\epsilon )D$, while every pair hypergraph codegree is one. For any proposed $\delta >0$, choose $m$ large enough that $1\le \delta D$. Nevertheless a matching in a graph contains at most $11m$ edges, whereas there are $(22m+1)11m$ edges in total. Thus every edge coloring requires at least $22m+1$ colours, exceeding $(1+\epsilon )D=22m$. The obstruction persists with arbitrarily small relative hypergraph codegree.

The meaningful asymptotic target separates the output tolerance from the input regularity error. For fixed rank $r$ and target $\eta >0$, choose a sufficiently small $\delta =\delta (r,\eta )$ and require degrees in $[(1-\delta )D,(1+\delta )D]$ as well as pair hypergraph codegrees at most $\delta D$. The semi-random method then gives ${\chi }^{\prime }(G)\le (1+\eta )D$. Here is the requested proof essay for that corrected conclusion, including its random rounds, tracking requirements and completion step.

A useful way to run all colour classes together is the auxiliary matching construction for hypergraph edge colouring. Use $K=\lceil D\rceil$ initial colours. Create a task vertex for each original edge $e$, and a resource vertex $(v,c)$ for each original vertex and colour. An assignment $(e,c)$ is an $(r+1)$-edge consisting of its task and the resources $(v,c)$ for all $v\in e$. A matching in a hypergraph in this auxiliary system is a proper partial colouring: a task cannot get two colours, and two edges sharing $v$ cannot use the same resource $(v,c)$.

The auxiliary task degrees are $K$, resource degrees are $d_G(v)$, and its pair hypergraph codegrees are at most $\max (1,\delta D)$. It is therefore nearly regular with small hypergraph codegrees. For $r\ge 2$ and a nonempty original hypergraph, the hypergraph codegree condition also forces $D\ge 1/\delta$; taking $\delta$ small absorbs rounding and ensures a large working degree. Rank one is immediate by assigning distinct colours to edges at each vertex.

The extra balance condition is important. Let $S_v$ be the set of tasks corresponding to edges through original vertex $v$. A matching in a hypergraph missing a small fraction of all tasks need not leave few tasks in each $S_v$. The Rödl nibble must leave at most $\beta D$ unmatched tasks in every such star, where one may choose $\beta =\eta /(4r)$. This local requirement, rather than just a global almost-perfect matching in a hypergraph, is what permits a cheap final edge colouring.

Run a Rödl nibble on the auxiliary system, whose rank is $s=r+1$. In a round of working degree $D_j$, sample each surviving assignment independently with probability $\alpha /D_j$, for a small fixed $\alpha$. Accept the sampled assignments that meet no other sampled assignment. Delete every auxiliary vertex touched by any sampled assignment, including conflicted ones, before proceeding. The accepted assignments are a matching in a hypergraph, and later assignments cannot reuse a consumed task or resource. Record each discarded but uncoloured task as waste; it must be counted in the final residual graph.

For an auxiliary vertex of degree $(1\pm \xi )D_j$, the probability of remaining untouched isFor an auxiliary edge through a surviving vertex, the other $s-1$ vertices survive with probability approximately $e^{-(s-1)\alpha }$. Their incident trial families overlap in at most $O_s(\delta D)$ trials by the hypergraph codegree bound, so the overlap error in this product calculation is small. This leads to the degree trajectorywhile the surviving fraction of task vertices is approximately $e^{-\alpha }$ per round. For a sampled assignment, a union bound over at most $s(1+O(\xi ))D_j$ conflicting assignments gives collision probability at most $s\alpha (1+O(\xi ))$. More explicitly, for a fixed task the expected number of ordered sampled conflict pairs having the first assignment through that task is at mostThis bounds its waste probability. Thus productive deletion is first order in $\alpha$, and collision loss is second order.

The technical tracking step makes these expected value calculations locally simultaneous and keeps their errors from accumulating. Its requirements are: residual auxiliary degrees stay near their trajectory after controlled pruning; each original star has the predicted number of surviving tasks; and every star's total collision and pruning waste is small. The standard probabilistic tools enter at distinct points.

Within a fixed round, task-survival indicators are independent: trial families for different tasks are disjoint, even when their assignments share resources. Conditional Chernoff bounds therefore control the number of surviving tasks in each star. Collision loss has short certificates consisting of pairs of selected intersecting assignments. The number selected through one resource has a binomial distribution of bounded mean. Chernoff bounds truncate these numbers at a suitable logarithmic cutoff; after truncation one trial has only a logarithmically bounded effect on the certified collision count. A certifiable function concentration bound, or a corresponding exposure argument, then controls loss in each star. These rare local overload events have polynomially bounded local dependency neighborhoods in the working degree, so the Lovász local lemma can select a simultaneous outcome independent of the total number of vertices.

Residual-degree counts require additional care because they are not sums of independent indicators. Two survival tests share at most a hypergraph codegree's worth of trials; expanding their joint probabilities bounds their covariance by the corresponding relative overlap. For a residual-degree count $Z$ with $D_j$ summands, overlapping summands and shared survival trials give a variance bound of the formChebyshev's inequality then bounds $\mathrm{Pr}(|Z-\mathbb{E}Z|>\xi D_j)$ by $C_s(D_j^{-1}+\zeta )/{\xi }^2$. This gives a small exceptional fraction when the relative hypergraph codegree is sufficiently small; it does not by itself make every degree good. The tracking argument records and prunes these exceptional configurations, bounding their contribution to each star by codegree-weighted exposure and the same local-loss bookkeeping. Markov's inequality controls exceptional mass, and repeated conditional concentration controls the retained counts. One must not apply an independent Chernoff bound directly to a residual degree or infer a uniform star bound just from a global expected loss. Keeping the pruning loss explicitly is the key distinction between a valid Rödl nibble argument and those shortcuts.

Choose the parameters in this order: first $r,\eta$ and $\beta$; next $\alpha$ so small that $s\alpha \log (4/\beta )\ll \beta$; nextand finally the initial regularity/hypergraph codegree tolerance $\delta$ small enough for all $T$ tracking and pruning errors. This is a bounded number of rounds depending on the tolerances, not on the graph order. After $T$ rounds, the surviving task fraction is at most approximately $\beta /4$, while accumulated collision loss is $O_s(T{\alpha }^2)=O_s(\alpha \log (4/\beta ))$. Reserving the remaining margin for tracking and pruning leaves at most $\beta D$ uncoloured edges at every original vertex. The working degree is still a fixed positive multiple of $D$, namely about $D{e}^{-r\alpha T}$, so the large-degree estimates remain applicable throughout.

Finally use a fresh palette on the residual original hypergraph. Its maximum degree is at most $\beta D$; an edge meets at most $r(\beta D-1)$ others. Greedy colouring therefore needs at most $r\beta D+1$ fresh colours. The total is at mostfor sufficiently large $D$, already ensured by choosing $\delta$ small. This completes the passage from the locally balanced Rödl nibble to the hypergraph chromatic index bound. The degree tolerance must be the small input parameter $\delta$; replacing it by the entire output allowance $\eta$ removes the slack and leads precisely to the complete-graph counterexample above.

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.