南京大学：《组合数学 Combinatorics》课程教学资源（课件讲稿）Extremal Combinatorics

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 E is maximized for complete balanced bipartite graph for arbitrary G?

Triangle-free graph contains no as subgraph Example: bipartite graph |E| is maximized for complete balanced bipartite graph for arbitrary G?

Mantel's Theorem Theorem (Mantel 1907) If G(V,E)has IV=n and is triangle-free,then 22 |E1≤ 4 For n is even, extremal graph:

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 n →G2△ 4 Induction step:for n=N due to I.H.E(B)<(n-2)2/4 A |E(A,B)川=|E-|E(B)川-1 n2_m-22-1=n-2 4 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→El≤n2/4 Second Proof. ∑(d+d)=d uw∈E u∈V △-free→du+d,≤n→∑(du+du)≤nlEl uv∈E Cauchy-Schwarz ( 2 4E2 (handshaking） m w∈V mE≥∑d+d)=∑≥②ev4)°- 4E2 m uv∈E v∈V m

-free 㱺 |E| ≤ n2/4 Second Proof. ￾ uv￾E (du + dv) = ￾ v￾V d2 v u v (du + dv) Cauchy-Schwarz ⇤ v￾V d2 v ￾ 1 n ￾⇤ v￾V dv ⇥2 = 4|E| 2 n -free ⇥ du + dv ￾ n ⇥ ￾ uv￾E (du + dv) ￾ n|E| n|E| ￾ ⌅ uv￾E (du + dv) = ⌅ v￾V d2 v ￾ ￾⇤ v￾V dv ⇥2 n = 4|E| 2 n (handshaking)

△-free→lEl≤n2/4 Second Proof. 为8 >(d+d)=d uw∈E u∈V △-free→du+dv≤n→(du+d)≤nlEl uu∈E Cauchy-Schwarz 呢(a) 4E2 (handshaking) w∈V V m nE≥ 4E2 > E≤ 2 m 4

-free 㱺 |E| ≤ n2/4 Second Proof. ￾ uv￾E (du + dv) = ￾ v￾V d2 v Cauchy-Schwarz ⇤ v￾V d2 v ￾ 1 n ￾⇤ v￾V dv ⇥2 = 4|E| 2 n -free ⇥ du + dv ￾ n ⇥ ￾ uv￾E (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 lAl independent v∈V,d≤a dv B=V\A B incident to all edges B=B ⊙和 Inequality of the arithmetic and geometric mean B 因≤sa时s(2）f- 4 u∈B

-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| ￾ ￾ v￾B dv = n2 4 Inequality of the arithmetic and geometric mean

Turan's Theorem "Suppose G is a K-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 Iv=n and is K,-free,then E卧≤ r-2n2 (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