Extremal Combinatorics "how large or how small a collection of finite objects can be,if it has to satisfy certain restrictions
Extremal Combinatorics “how large or how small a collection of finite objects can be, if it has to satisfy certain restrictions
Extremal Problem: "What is the largest number of edges that an n-vertex cycle-free graph can have?" (n-1) Extremal Graph: spanning tree
“What is the largest number of edges that an n-vertex cycle-free graph can have?” Extremal Problem: Extremal Graph: (n-1) spanning tree
Triangle-free graph contains no△，as subgraph Example:bipartite graph is maximized for complete balanced bipartite graph Extremal
Triangle-free graph contains no as subgraph Example: bipartite graph |E| is maximized for complete balanced bipartite graph Extremal ?
Mantel's Theorem Theorem (Mantel 1907) If G(V,E)has IV=n and is triangle-free,then n2 E≤ 4 For n is even, extremal graph: K受，号
Mantel’s Theorem Theorem (Mantel 1907) |E| n2 4 . If G(V,E) has |V|=n and is triangle-free, then For n is even, extremal graph: K n 2 , n 2
△-free→lEl≤n2/4 First Proof.Induction on n. Basis:n=1,2.trivial Induction Hypothesis:for any nN n2 1E> →G2△ 4 Induction step:for n=N due to I.H.E(B)<(n-2)2/4 7 E(A,B)川=|E-|E(B)川-1 n2_ 4 m-22-1=n-2 4 pigeonhole!
Induction on n. Induction Hypothesis: for any n 㱺 G ⊇ n2 4 First Proof. A B due to I.H. |E(B)| ≤ (n-2)2/4 |E(A, B)| = |E| |E(B)| 1 > n2 4 (n 2)2 4 1 = n 2 pigeonhole!
△-free→lEl≤n2/4 Second Proof. (d+d)=∑d品 uv∈E w∈V △-free→du+d,≤n→(d+dw)≤nlE uu∈E Cauchy-Schwarz 4E2 (handshaking） m n网≥d+d)=上e区a- 4E2 m uU∈E m
-free 㱺 |E| ≤ n2/4 Second Proof. uvE (du + dv) = vV d2 v u v (du + dv) Cauchy-Schwarz ⇤ vV d2 v 1 n ⇤ vV dv ⇥2 = 4|E| 2 n -free ⇥ du + dv n ⇥ uvE (du + dv) n|E| n|E| ⌅ uvE (du + dv) = ⌅ vV d2 v ⇤ vV dv ⇥2 n = 4|E| 2 n (handshaking)
△，-free→lEl≤n2/4 Second Proof. ∑(d+d)=∑品 uw∈E w∈V △-free→d,+d≤n→ ∑(d.+d)≤mE uU∈E Cauchy-Schwarz 4E2 (handshaking) m nE≥ 4E2 n2 > E≤ m 4
-free 㱺 |E| ≤ n2/4 Second Proof. uvE (du + dv) = vV d2 v Cauchy-Schwarz ⇤ vV d2 v 1 n ⇤ vV dv ⇥2 = 4|E| 2 n -free ⇥ du + dv n ⇥ uvE (du + dv) n|E| n|E| 4|E| 2 n (handshaking) |E| n2 4 u v (du + dv)
△-free→lEl≤n2/4 Third Proof. A:maximum independent set a IAl independent v∈V,d,≤a B=V\A B incident to all edges B=IBl Inequality of the arithmetic and geometric mean B scaa≤(2)-
-free 㱺 |E| ≤ n2/4 Third Proof. A: maximum independent set B = V \ A α = |A| β = |B| v ⇤ ⇥ ⌅ dv independent ⇤v ⇥ V, dv B B incident to all edges ⇥ + ⇥ 2 ⇥2 |E| vB dv = n2 4 Inequality of the arithmetic and geometric mean
Turan's Theorem "Suppose G is a Kr-free graph. What is the largest number of edges that G can have?" Paul Turan (1910-1976)
Turán's Theorem Paul Turán (1910-1976) “Suppose G is a Kr -free graph. What is the largest number of edges that G can have?
Turan's Theorem Theorem(Turan 1941) If G(V,E)has IVl=n and is K,-free,then r-2 E≤ n2. 2(r-1
Turán's Theorem Theorem (Turán 1941) If G(V,E) has |V|=n and is Kr-free, then |E| ⇥ r 2 2(r 1)n2