Extremal CombinatoricsInstructor: Jie Ma, Scribed by Yihan Chen, Ke Fang, Jun Gao, Hongjun Ge, Jinye He,Nianxin Ren,Zelin Ren, Mingyuan Rong, Yuxuan Tang, Hongyu Wang, YuntaoWang,YuzeWu,Dapeng Xu, Miao Xu, Tianchi Yang, Zhi Yi, Wanchen Zhang,Yuanwen ZhengZhihen ZhengJuly 6th, 2021, TuesdayContents3Turan'sTheoremandKovari-Sos-TuranTheorem131.1TuranDensity.31.2 Mantel's Theorem31.3Turan's Theorem41.4 Kovari-Sos-Turan Theorem52Hypergraph KsT, Supersaturation Lemma52.1Erdos-MoonTheorem2.25Hypergraph Kovari-Sos-Turan Theorem2.36Supersaturation Lemma73Blowup Lemma and Erdos-Stone-Simonovits Theorem73.1Blowup Lemma3.2Erdos-Stone-Simonovits Theorem783.3QuantitativeVersionofErdos-Stone-Simonovits Theorem10Bondy-Simonovits Theorem on Even Cycles44.1The First Proof .104.211The Second Proof .4.3The Third Proof12195 Even-cycle-free Subgraphs of the Hypercube5.1 TheFirstProof of Theorem 5.2byFuredi-Ozkahya205.2The Second Proof by D. Conlon22246 Spectral Graph Theorem256.1Courant-FischerTheorem6.2Cheeger's Inequality276.3 Graphic Inequalities28306.4 Cayley Graphs337.Godsil-NewmanTheorem1
Extremal Combinatorics Instructor: Jie Ma, Scribed by Yihan Chen, Ke Fang, Jun Gao, Hongjun Ge, Jinye He, Nianxin Ren, Zelin Ren, Mingyuan Rong, Yuxuan Tang, Hongyu Wang, Yuntao Wang, Yuze Wu, Dapeng Xu, Miao Xu, Tianchi Yang, Zhi Yi, Wanchen Zhang, Yuanwen Zheng, Zhihen Zheng July 6th, 2021, Tuesday Contents 1 Tur´an’s Theorem and K¨ovari-S´os-Tur´an Theorem 3 1.1 Tur´an Density . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Mantel’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Tur´an’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.4 K¨ovari-S´os-Tur´an Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2 Hypergraph KST, Supersaturation Lemma 5 2.1 Erd¨os-Moon Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2 Hypergraph K¨ovari-S´os-Tur´an Theorem . . . . . . . . . . . . . . . . . . . . . . . . 5 2.3 Supersaturation Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 3 Blowup Lemma and Erd˝os-Stone-Simonovits Theorem 7 3.1 Blowup Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 3.2 Erd˝os-Stone-Simonovits Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 3.3 Quantitative Version of Erd˝os-Stone-Simonovits Theorem . . . . . . . . . . . . . . 8 4 Bondy-Simonovits Theorem on Even Cycles 10 4.1 The First Proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 4.2 The Second Proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 4.3 The Third Proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 5 Even-cycle-free Subgraphs of the Hypercube 19 5.1 The First Proof of Theorem 5.2 by F¨uredi -Ozkahya . . . . . . . . . . . . . . . . . ¨ 20 5.2 The Second Proof by D. Conlon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 6 Spectral Graph Theorem 24 6.1 Courant-Fischer Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 6.2 Cheeger’s Inequality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 6.3 Graphic Inequalities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 6.4 Cayley Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 7 Godsil-Newman Theorem 33 1
368 Random Walk368.1 Definition378.2TheConvergenceof LazyRandom Walk399Cheeger'sInequality4210 Alon Boppana Lower Bound4411 Bipartite Ramanujan Graph4411.1 2-Lift4511.2 Matching Polynomial4911.3InterlaceFamily5212 Expander Graphs5312.1 Expanders as Approximations of the Complete Graph5312.2 Quasi-random Properties of Expanders:5713 The Second Proof of Cheeger's Inequality5914Iterative Solvers for Linear Equations5914.1 First-orderIteration14.2 Another Method606014.3ChebyshevPolynomials6115An Application of Borsuk-UlamTheorem2
8 Random Walk 36 8.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 8.2 The Convergence of Lazy Random Walk . . . . . . . . . . . . . . . . . . . . . . . . 37 9 Cheeger’s Inequality 39 10 Alon Boppana Lower Bound 42 11 Bipartite Ramanujan Graph 44 11.1 2-Lift . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 11.2 Matching Polynomial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 11.3 Interlace Family . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 12 Expander Graphs 52 12.1 Expanders as Approximations of the Complete Graph . . . . . . . . . . . . . . . . 53 12.2 Quasi-random Properties of Expanders . . . . . . . . . . . . . . . . . . . . . . . . . 53 13 The Second Proof of Cheeger’s Inequality 57 14 Iterative Solvers for Linear Equations 59 14.1 First-order Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 14.2 Another Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 14.3 Chebyshev Polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 15 An Application of Borsuk-Ulam Theorem 61 2
1Turan's Theorem and Kovari-Sos-Turan TheoremLet us begin this course by introducing some basic notations in graph theory. Let G = (V, E) be agraph. The degree d(u) of a vertex v is the number of neighbors of . Let (G) := max(d(u)u EVl bethe marimum degree of G and s(G) := minfd(o)luE Vbethe minimum degree. Thecomplete graph on n vertices is denoted by Kn, while the complete r-partite graph with parts ofsizes ni, n2,... n, s denoted by Kni,n2...n.Let F be a family of graphs. A graph G is called F-free if G contains none of F as a subgraph.Let ex(n, F) denote the largest possible number of edges in an n-vertex F-free graph, and call itthe Turan number or ertremal number of F.1.1TuranDensityIf F be a family of graphs, the Turain density of F is denoted by (F)= lim. (g. We can+00()prove the following.Theorem 1.1. r(F) eaists for any family F.Proof. Let n = ex(n, F)/(2), then Tn e [0, 1]. It suffices to show that [n) is non-increasing.Let G be an n-vertex F-free graph with ex(n, F) edges. By double-counting the number of pairs(e,T) where eE G[T) and T C (n-), we can get#(e, T)= Z= (n - 2)ex(n, F)(n-eEE(G)and#(e,T) = e(G[T)≤n·ex(n-1,F),TC(V()Together we have (n-2)ex(n, F)≤ n ex(n -1,F), implying that πn ≤ n-1, as desired.1.2Mantel'sTheoremTheorem 1.2 (Mantel). If G is an n-verter K3-free graph, then e(G) ≤ ] with equality if andonly if G=K1Proof. We will prove it by induction on n. It is trivial for n ≤ 3. So assume n ≥ 4. By deletingsome edges, we can also assume e(G) = []. Then there exists a vertex u with d(v) ≤ [J. LetG'= G- (u). Clearly G' is an (n-1)-vertex K3-free graph with e(G') ≥[]-[号]=[-1}].By induction, weknow G'=K[J[ with two parts A,B. Also it iseasy to see that N(o)is a subset of A or B. Otherwise, there exists a K3 in G. Then one can verify that N(u) = A or1N(u) = B and thus G = KJ[11.3Turan's TheoremLet Turan graph T,(n) be the complete balanced r-partite graph on n ≥ r vertices.That isV = ViU V2... u V and [Vil = ["] or ["], such that all pairs in V, × V, form edges.Before proving the Turan's Theorem, let us show three easy observations on T(n) as follows.3
1 Tur´an’s Theorem and K¨ovari-S´os-Tur´an Theorem Let us begin this course by introducing some basic notations in graph theory. Let G = (V, E) be a graph. The degree d(v) of a vertex v is the number of neighbors of v. Let ∆(G) := max{d(v)|v ∈ V } be the maximum degree of G and δ(G) := min{d(v)|v ∈ V } be the minimum degree. The complete graph on n vertices is denoted by Kn, while the complete r-partite graph with parts of sizes n1, n2, ., nr is denoted by Kn1,n2,.,nr . Let F be a family of graphs. A graph G is called F-free if G contains none of F as a subgraph. Let ex(n, F) denote the largest possible number of edges in an n-vertex F-free graph, and call it the Turan number or extremal number of F. 1.1 Tur´an Density If F be a family of graphs, the Tur´an density of F is denoted by π(F) = lim n→+∞ ex(n,F) ( n 2 ) . We can prove the following. Theorem 1.1. π(F) exists for any family F. Proof. Let πn = ex(n, F)/ n 2 , then πn ∈ [0, 1]. It suffices to show that {πn} is non-increasing. Let G be an n-vertex F-free graph with ex(n, F) edges. By double-counting the number of pairs (e, T) where e ∈ G[T] and T ⊆ G n−1 , we can get #(e, T) = X e∈E(G) n − 2 n − 3 = (n − 2)ex(n, F) and #(e, T) = X T ⊆( V (G) n−1 ) e(G[T]) ≤ n · ex(n − 1, F). Together we have (n − 2)ex(n, F) ≤ n · ex(n − 1, F), implying that πn ≤ πn−1, as desired. 1.2 Mantel’s Theorem Theorem 1.2 (Mantel). If G is an n-vertex K3-free graph, then e(G) ≤ bn 2 4 c with equality if and only if G = Kb n 2 cd n 2 e . Proof. We will prove it by induction on n. It is trivial for n ≤ 3. So assume n ≥ 4. By deleting some edges, we can also assume e(G) = b n 2 4 c. Then there exists a vertex v with d(v) ≤ bn 2 c. Let G0 = G − {v}. Clearly G0 is an (n − 1)-vertex K3-free graph with e(G0 ) ≥ bn 2 4 c − bn 2 c = b (n−1)2 4 c. By induction, we know G0 = Kb n−1 2 cd n−1 2 e with two parts A, B. Also it is easy to see that N(v) is a subset of A or B. Otherwise, there exists a K3 in G. Then one can verify that N(v) = A or N(v) = B and thus G = Kb n 2 cd n 2 e . 1.3 Tur´an’s Theorem Let Tur´an graph Tr(n) be the complete balanced r-partite graph on n ≥ r vertices. That is V = V1 ∪ V2. ∪ Vr and |Vi | = b n r c or d n r e, such that all pairs in Vi × Vj form edges. Before proving the Tur´an’s Theorem, let us show three easy observations on Tr(n) as follows. 3
(i) e(T,(n)) =[n+iJln+iJ achieves the unique maximum in all n-vertex r-partite graphs.(ii) T,(n - 1) = T,(n) -[u), where d(u) = (T,(n)) = n - [].(i) T,(n) has the highest minimum degree among all n-vertex graphs with the same number ofedges.Next, we will give two different proofs based on above observations.Theorem 1.3 (Turan). Let G be an n-verter Kr+1-free graph. Then e(G) ≤ e(T,(n)) withequality holds if and only if G = T,(n).Proof. (first): We prove it by induction on n. The base case n = r is clear. Let n ≥ r +1.By observation (ii), there exists a vertex with d(u) ≤ (T,(n)). Let G' = G - [u). We seee(G') = e(G) - d(u) ≥ e(Tr(n)) - (Tr(n) = e(Tr(n -1)). By induction, we know G' = T,(n -1),Then we claim that G is a r-partite graph. As otherwise, each part of G' contains a neighbor ofu, implying that these r vertices together with form a Kr+1. Hence by (i) we get G = T,(n). Proof. (second): Let us prove it by induction on r. It is clear that Mantel's Theorem gives thecase for r = 2. Assume r ≥ 3. Let u E V(G) with d(u) = △(G). Let S = N(u) and T = V\SWe see G[S] is Kr-free. Now let G' be obtained from G by deleting all edges in G[T] and addingall missing edges in (S, T). Then we see G' is Kr+i-free. And the number of missing edges in(S, T) is |S/T- eG(S, T). Now we claim that e(G') = e(G) and e(G[T)) = 0. Since2e(G[T)) +eG(S, T) = dG(r) ≤△(G)IT| = |SITI,ETwe havee(G') = e(G) - e(G[T)) + (ISIIT| - eG(S, T)) ≥ e(G) + e(G[T)This confirms the claim. Clearly G = G'. We see G[S] is K,-free and contain the maximumnumber of edges on |S| vertices. By induction we know G[S] must be (r - 1)-partite. Thus G is-r-partite. Finally, by (i) we get G = T(n).Next, we consider the Turan number of complete bipartite graphs.1.4Kovari-Sos-Turan TheoremTheorem 1.4 (Kovari-Sos-Turan). For any integers t ≥ s ≥> 2, we haveex(n, Ks,) ≤(t - 1) n2-I +((s -1)n2Proof. Let G be any n-vertex Ks.t-free graph. Let the number of stars Ki.,in G be T. On theone hand, for a fixed vertex u, there are (dc(o) many Ki,s rooted at it. Then T = (dc(o).VEV(G)Here we definer(α-1).-(c-$+1)≥sotherwise.04
(i) e(Tr(n)) = P 0≤i<j<r b n+i r cbn+j r c achieves the unique maximum in all n-vertex r-partite graphs. (ii) Tr(n − 1) = Tr(n) − {v}, where d(v) = δ(Tr(n)) = n − dn r e. (iii) Tr(n) has the highest minimum degree among all n-vertex graphs with the same number of edges. Next, we will give two different proofs based on above observations. Theorem 1.3 (Tu´ran). Let G be an n-vertex Kr+1-free graph. Then e(G) ≤ e(Tr(n)) with equality holds if and only if G = Tr(n). Proof. (first): We prove it by induction on n. The base case n = r is clear. Let n ≥ r + 1. By observation (iii), there exists a vertex v with d(v) ≤ δ(Tr(n)). Let G0 = G − {v}. We see e(G0 ) = e(G)−d(v) ≥ e(Tr(n))−δ(Tr(n)) = e(Tr(n−1)). By induction, we know G0 = Tr(n−1). Then we claim that G is a r-partite graph. As otherwise, each part of G0 contains a neighbor of v, implying that these r vertices together with v form a Kr+1. Hence by (i) we get G = Tr(n). Proof. (second): Let us prove it by induction on r. It is clear that Mantel’s Theorem gives the case for r = 2. Assume r ≥ 3. Let u ∈ V (G) with d(u) = ∆(G). Let S = N(u) and T = V \S. We see G[S] is Kr-free. Now let G0 be obtained from G by deleting all edges in G[T] and adding all missing edges in (S, T). Then we see G0 is Kr+1-free. And the number of missing edges in (S, T) is |S||T| − eG(S, T). Now we claim that e(G0 ) = e(G) and e(G[T]) = 0. Since 2e(G[T]) + eG(S, T) = X x∈T dG(x) ≤ ∆(G)|T| = |S||T|, we have e(G 0 ) = e(G) − e(G[T]) + (|S||T| − eG(S, T)) ≥ e(G) + e(G[T]). This confirms the claim. Clearly G = G0 . We see G[S] is Kr-free and contain the maximum number of edges on |S| vertices. By induction we know G[S] must be (r − 1)-partite. Thus G is r-partite. Finally, by (i) we get G = Tr(n). Next, we consider the Tur´an number of complete bipartite graphs. 1.4 K¨ovari-S´os-Tur´an Theorem Theorem 1.4 ( K¨ovari-S´os-Tur´an). For any integers t ≥ s ≥ 2, we have ex(n, Ks,t) ≤ 1 2 (t − 1) 1 s n 2− 1 s + 1 2 (s − 1)n. Proof. Let G be any n-vertex Ks,t-free graph. Let the number of stars K1,s in G be T. On the one hand, for a fixed vertex v, there are dG(v) s many K1,s rooted at it. Then T = P v∈V (G) dG(v) s . Here we define x s = x(x−1)···(x−s+1) s! , x ≥ s 0, otherwise. 4
On the other hand,for anyfixed s vertices, there are at most t-1 vertices which are adjacentto all these s vertices. Thus we have T ≤ (t -1)(n)Combining them and using Jensen's inequality, we get(Zvev(G) de(u) /n) ≥ n. (2e(G)/n =8 + 1)(dg(u)))≥≥(t-1)(≥n(t - 1)s!sVEV(G)Thus we have e(G) ≤(t - 1):n2-1 + (s - 1)n.IThese theorems also tell us that r(Kr+1) = 1 - ↓ and r(Ks,t) = 0 for any integers r, s, t ≥ 1.2Hypergraph KST, Supersaturation Lemma2.1Erdos-MoonTheoremTheorem 2.1 (Erdos-Moon). Let G be an n-verte graph with more than s1+1/sn2-1/s + 2snedges. Then it has at least 2(ps"n2s) copies of Ks,s, where p= e(G)/(2) is the edge-density of G.Proof. Let M denote the number of stars Ki,s in G. We see M = Zvev (d(o). For a subsetS C V(G) of size s, let f(S) be the number of vertices adjacent to all vertices of S. Then we seeM-se() (S). And G has Zse() (($) copies of Kss. By Jensen's iequality, we alsoget2 ()≥()(2se((5)/)≥()(/)-n(a-)SE(=0(n- (() ≥2(ar-)((Ze d(0)/n)) = 2(p n2s)PP.2.2 Hypergraph Kovari-Sos-Turan TheoremLt etecoetertteroenee wedoe KFor a k-graph G and E V(G), the link-hypergraph Gu is a (k - 1)-graph on the vertex setV(G) - [u) where e E E(Gu) if and only if eU [u) E E(G).Theorem 2.2 (Erdos). Let k,t ≥ 2 be integers. Then there erists a constant c = c(k,t) suchthat any k-graph G with e(G) =p(r) ≥ cnk-(1/t)k-1 has at least 2(pt'ntk) copies of Kt:k.Proof.We prove this by induction on k.It is clear that the Erdos-Moon theorem gives thecase for k = 2. We may assume it holds for k - 1 with k ≥ 3. Suppose G is a k-graph withcnk-(1/t)-1 edges. Let Vi = (u e V(G) : d(u) ≥ cn(k-1)-(1/t)-) and V2 = V(G) / Vi. ThenZvg)s d(o) n.cn(-1)-(/)x-"e(G) implying that Zven d(0) =(k=0(1)e(C):For each u e Vi, the link-hypergraph G, is a (k - 1)-graph with e(G,) = d(u). By induction,~ (n - 1)(k-1) )) = 2(nt(x-1)-(k-1)k-1)d(u)*-1 copies of Kt(k-1)Gu has at least 25
On the other hand, for any fixed s vertices, there are at most t−1 vertices which are adjacent to all these s vertices. Thus we have T ≤ (t − 1) n s . Combining them and using Jensen’s inequality, we get (t − 1)n s s! ≥ (t − 1) n s ≥ X v∈V (G) dG(v) s ≥ n P v∈V (G) dG(v)/n s ≥ n · (2e(G)/n − s + 1)s s! . Thus we have e(G) ≤ 1 2 (t − 1) 1 s n 2− 1 s + 1 2 (s − 1)n. These theorems also tell us that π(Kr+1) = 1 − 1 r and π(Ks,t) = 0 for any integers r, s, t ≥ 1. 2 Hypergraph KST, Supersaturation Lemma 2.1 Erd¨os-Moon Theorem Theorem 2.1 (Erd¨os-Moon). Let G be an n-vertex graph with more than 1 2 s 1+1/sn 2−1/s + 2sn edges. Then it has at least Ω(p s 2 n 2s ) copies of Ks,s, where p = e(G)/ n 2 is the edge-density of G. Proof. Let M denote the number of stars K1,s in G. We see M = P v∈V d(v) s . For a subset S ⊆ V (G) of size s, let f(S) be the number of vertices adjacent to all vertices of S. Then we see M = P S∈( V s ) f(S). And G has 1 2 P S∈( V s ) f(S) s copies of Ks,s. By Jensen’s inequality, we also get 1 2 X S∈( V s ) f(S) s ≥ 1 2 n s P S∈( V s ) f(S)/ n s s ≥ 1 2 n s M/ n s s = Ω(n s−s 2 )Ms = Ω(n s−s 2 ) X v∈V d(v) s !s ≥ Ω(n s−s 2 ) n P v∈V d(v)/n s s = Ω(p s 2 n 2s ). 2.2 Hypergraph K¨ovari-S´os-Tur´an Theorem Let K (k) (t1,t2,.,tk) be the complete k-partite k-graph. For convenience, we denote Kt:k = K (k) (t,t,.,t) . For a k-graph G and v ∈ V (G), the link-hypergraph Gv is a (k − 1)-graph on the vertex set V (G) − {v} where e ∈ E(Gv) if and only if e ∪ {v} ∈ E(G). Theorem 2.2 (Erd˝os). Let k, t ≥ 2 be integers. Then there exists a constant c = c(k, t) such that any k-graph G with e(G) = p n k ≥ cnk−(1/t) k−1 has at least Ω(p t k n tk) copies of Kt:k. Proof. We prove this by induction on k. It is clear that the Erd¨os-Moon theorem gives the case for k = 2. We may assume it holds for k − 1 with k ≥ 3. Suppose G is a k-graph with cnk−(1/t) k−1 edges. Let V1 = {v ∈ V (G) : d(v) ≥ cn(k−1)−(1/t) k−2 } and V2 = V (G) \ V1. Then P v∈V2 d(v) ≤ n · cn(k−1)−(1/t) k−2 e(G), implying that P v∈V1 d(v) = (k − o(1))e(G). For each v ∈ V1, the link-hypergraph Gv is a (k − 1)-graph with e(Gv) = d(v). By induction, Gv has at least Ω e(Gv) ( n−1 k−1 ) t k−1 · (n − 1)t(k−1)! = Ω(n t(k−1)−(k−1)t k−1 )d(v) t k−1 copies of Kt:(k−1). 5