Alphabeta MathExtremal Graph Theory
About this page
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.
✓ 16 results · all verified · 0 also independently AI-judged
Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs. The 16 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.
1 · Prerequisites
Combinatorics
Real Analysis
- Construction of the Real Numbers via Cauchy Sequences
- Construction of the Real Numbers via Dedekind Cuts
- Countability and Uncountability
- Foundations of the Real Numbers for Analysis
- Monotone Sequences, Bolzano-Weierstrass, and Cauchy Completeness
- Roots, Rational Powers, and Classical Inequalities
- Sequences and Limits
- Suprema and Infima
2 · Logical flowchart
3 · Items
Definition
Ordinary-subgraph extremal number ex(n,H), Turán graph T_n,r, and balanced blowup H[s]
Lemma
The exact edge count of T_n,r and the unique balancing maximum among complete r-partite graphs
Theorem
Mantel's theorem: ex(n,K₃)=⌊ n²/4⌋, uniquely attained by T_n,2
Lemma
Zykov symmetrisation turns an extremal clique-free graph into a complete multipartite graph without losing edges
Theorem
Turán's theorem with equality: ex(n,Kᵣ₊₁)=e(T_n,r), and T_n,r is the unique extremal graph
Corollary
Turán graphs give the Ramsey lower bound R(s,t)≥(s-1)(t-1)+1
Definition
Edge density and the asymptotic notations O, o, Ω, and Θ for extremal functions
Proposition
ex(n,H)/C(n, 2) is nonincreasing for n≥2
Theorem
Every finite graph with an edge has a Turán density π(H)=lim_n→∞ex(n,H)/C(n, 2)
Theorem
Above Turán density, a graph contains a positive-density family of copies of the forbidden graph
Definition
The Zarankiewicz number z(m,n;s,t) for a forbidden K_s,t in a bipartite graph
Lemma
The Kővári–Sós–Turán common-neighbour count and the discrete convexity lower bound for degree sums
Theorem
Kővári–Sós–Turán: exact bipartite and ordinary-graph upper bounds for excluding K_s,t
Corollary
Every bipartite graph with at least one edge has Turán density zero
Definition
r-uniform hypergraphs and complete balanced r-partite r-graphs K⁽ʳ⁾_s,…,s
Theorem
Hypergraph KST: ex(n,K⁽ʳ⁾_s,…,s)=O_r,s(n^r-1/sʳ⁻¹)=o(nʳ)
Lemma
Every finite graph H with χ(H)=r is an ordinary subgraph of Kᵣ[s] for some s
Theorem
Erdős–Stone for balanced blowups: π(Kᵣ[s])=1-1/(r-1) for r≥2
Theorem
Erdős–Stone–Simonovits: ex(n,H)=(1-1/(χ(H)-1)+o(1))C(n, 2) for every graph with an edge
Corollary