TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passaudited 2026-08-13

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Hypergraph KST: $ex (n, K_{s, \dots, s}^{(r)}) = O_{r, s} (n^{r - 1 / s^{r - 1}}) = o (n^{r})$

Statement

For fixed integers $r \geq 2$ and $s \geq 2$ ,

$ex (n, K_{s, \dots, s}^{(r)}) = O_{r, s} ⁣ (n^{r - 1 / s^{r - 1}}) = o (n^{r}) .$

Facts & Assumptions

Given: The hypotheses and notation of the statement above.

[F1]

An $r$ -uniform hypergraph has a finite vertex set and edges that are $r$ -element vertex sets; $K_{s, \dots, s}^{(r)}$ contains every transversal of its $r$ equal parts ( $r$ -uniform hypergraphs and complete balanced $r$ -partite $r$ -graphs $K_{s, \dots, s}^{(r)}$ ).

[F2]

For $s, t \geq 1$ , the Kővári–Sós–Turán theorem gives $ex (N, K_{s, t}) = O_{s, t} (N^{2 - 1 / s})$ (Kővári–Sós–Turán: exact bipartite and ordinary-graph upper bounds for excluding $K_{s, t}$ ).

[F3]

For a finite incidence relation, the sum of its row-fibre sizes equals the sum of its column-fibre sizes (Double counting: $\sum_{x \in X} ∣ R_{x} ∣ = ∣ R ∣ = \sum_{y \in Y} ∣ R^{y} ∣$ for a relation between finite sets).

[F4]

For a bipartite graph with parts of sizes $m, n$ containing no oriented $K_{s, t}$ with its $s$ vertices on the $m$ -side, the common-neighbour count is at most $(t - 1) (\binom{m}{s})$ ; for nonnegative integer degrees of total $E$ with $E / n \geq s - 1$ , smoothing gives the lower bound $n (E / n - s + 1)^{s} / s!$ (The Kővári–Sós–Turán common-neighbour count and the discrete convexity lower bound for degree sums).

[F5]

$f = O (g)$ means an eventual constant upper bound, $f = o (g)$ means $f / g \to 0$ , and subscripts permit the constants and thresholds to depend on those parameters (Edge density and the asymptotic notations $O$ , $o$ , $Ω$ , and $Θ$ for extremal functions).

Proof

technique · induction on uniformity through common links

1.1

For $r = 2$ , the ordinary KST theorem gives exponent $2 - 1 / s$ , which is the displayed exponent. Assume the result for uniformity $r - 1$ . Since the assertion is asymptotic, take $n \geq r - 1$ , and let an $r$ -graph $G$ on $n$ vertices have $M$ edges and contain no $K_{s, \dots, s}^{(r)}$ . For each $(r - 1)$ -set $A$ , let $d (A)$ be the number of vertices $v$ with $A \cup {v}$ an edge. Then $\sum_{A} d (A) = r M$ .

givenF1F2F3

2.1

Count pairs $(S, A)$ with $∣ S ∣ = s$ and every $v \in S$ extending $A$ to an edge. The count is $\sum_{A} (\binom{d (A)}{s})$ . For fixed $S$ , its common link is an $(r - 1)$ -graph containing no $K_{s, \dots, s}^{(r - 1)}$ , since such a copy together with $S$ would form the forbidden $r$ -partite $r$ -graph. By induction, $\sum_{A} (\binom{d (A)}{s}) = O_{r, s} (n^{s} n^{r - 1 - 1 / s^{r - 2}})$ .

step 1.1givenF1F3

3.1

If the average $r M / (\binom{n}{r - 1})$ is below $2 s$ , then $M = O_{r, s} (n^{r - 1})$ , already stronger than required. Otherwise degree smoothing gives $\sum_{A} (\binom{d (A)}{s}) = Ω_{r, s} (n^{r - 1} (M / n^{r - 1})^{s})$ . Comparing with step 2.1 and solving for $M$ gives $M = O_{r, s} (n^{r - 1 / s^{r - 1}})$ , because $r - 1 + s (1 - 1 / s^{r - 1}) = r + s - 1 - 1 / s^{r - 2}$ .

step 2.1givenalgebraF4

4.1

Induction proves the first asymptotic bound for every $r \geq 2$ . Since $1 / s^{r - 1} > 0$ , division by $n^{r}$ tends to $0$ , proving the $o (n^{r})$ clause.

step 1.1step 3.1givenF5∎

Depends on

Used by

Erdős–Stone for balanced blowups: π(Kᵣ[s])=1-1/(r-1) for r≥2 Theorem

Dependency tree · two levels

15 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Yufei Zhao, Graph Theory and Additive Combinatorics (standard reference, not scraped)

Hypergraph KST: ex⁡(n,Ks,…,s(r))=Or,s(nr−1/sr−1)=o(nr)ex(n,Ks,…,s(r)​)=Or,s​(nr−1/sr−1)=o(nr)