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<N n2 |E> →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 < N Induction step: for n = N Basis: n=1,2. trivial -free 㱺 |E| ≤ n2/4 |E| > 㱺 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!