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
Let S = (Si,.., Sk-1),whereSi|=t.We denote by f(S) the number of vertices such thatU..ia.iayK(..) in G associateswitha Kt:(k-1) inaunique G forev.Thus the number of k()(...) in G isf(S) ≥ 2(nt(k-1)-(k-1)tk-1) d(o)t-1VEViSWe already have Zuev d(u) = (k - o(1)e(G) and [Vil ≤ n. By Jensen's inequality, we can getd(u)Zf(S) ≥ 2(nt(k-1)-(k-1)tk-1) : n= 2(ptk-1 nt(k=1)+1),sFinally, the number of Kt:k in G is equal to(Zsf(S)(f(S))) ≥ 2(nt(k-1) (门≥ 2(nt(k-1)(pt*-In)t = 2(pt*nt*),nt(k-1This theorem gives us an upper bound for the extremal number of Kt:k as follows, and alsoimplies that (Kt:k) = 0.Theorem 2.3 (Hypergraph Kovari-Sos-Turan ).ex(n, Kt:k) = O(nk-(1/t)k-1),2.3 SupersaturationLemmaTheorem 2.4 (Supersaturation lemma). Let F be a k-graph with k ≥ 2. For any e > 0, thereerist positive constants =s(F,e) and no =no(F,e) such that for any n-verter k-graph G withn > no, if G has at least er(n, F)+e+nk edges, then it contains at least Sn copies of F, wherev = [V(F)L.Proof. By the definition of (F), we can find an integer m such that er(m', F) no > m. Assume the n-vertex k-graph G has (r(F) +e)(") edges. Weuse T to denote the number of pairs (e, M), where M e (m) and e E G[M]. On the one hand,we haven-k) =e(G)(“二条) =(F)+0()("二) =(F) +0(m)(1T=>eEE(G)On the other hand, if we let A = [M e ((C) : e(G[M) >(r(F) + )(")), then we getZ e(G[MI) = E e(G[M)+ E e(G[M) ≤[AI(m)+(T=)-{AI)((F)+)1MEAM$AMe(V(C)The above two inequalities indicate that ((F) + e)(m) ≤ [A| +(m) -[Al)((F) + ). So[A| ≥ (m)/(1 - -π(F)). Since each M E A satisfies e(G[M) > (π(F) +)(m) > er(m, F),we know G[M] has at least one copy of F. As each F can be contained in at most (m=u) choices(m)LAof M CA,wefinallygetthenumberofF-copiesinGisatleast=on".(1--元(F)(m-)(m-u)16
Let S~ = (S1, ., Sk−1), where |Si | = t. We denote by f(S~) the number of vertices v such that v ∪S1 ∪ · · · ∪Sk−1 induces a copy of K (k) (1,t,.,t) in G. Clearly each copy of K (k) (1,t,.,t) in G associates with a Kt:(k−1) in a unique Gv for v ∈ V . Thus the number of K (k) (1,t,.,t) in G is X S~ f(S~) ≥ Ω(n t(k−1)−(k−1)t k−1 ) X v∈V1 d(v) t k−1 . We already have P v∈V1 d(v) = (k − o(1))e(G) and |V1| ≤ n. By Jensen’s inequality, we can get X S~ f(S~) ≥ Ω(n t(k−1)−(k−1)t k−1 ) · n d(v) n t k−1 = Ω(p t k−1 n t(k−1)+1). Finally, the number of Kt:k in G is equal to 1 k X S~ f(S~) t ≥ Ω(n t(k−1)) P S~ f(S~) nt(k−1) !t ≥ Ω(n t(k−1))(p t k−1 n) t = Ω(p t k n tk). This theorem gives us an upper bound for the extremal number of Kt:k as follows, and also implies that π(Kt:k) = 0. Theorem 2.3 (Hypergraph K¨ovari-S´os-Tur´an ). exk(n, Kt:k) = O(n k−(1/t) k−1 ). 2.3 Supersaturation Lemma Theorem 2.4 (Supersaturation lemma). Let F be a k-graph with k ≥ 2. For any > 0, there exist positive constants δ = δ(F, ) and n0 = n0(F, ) such that for any n-vertex k-graph G with n > n0, if G has at least ex(n, F) + · n k edges, then it contains at least δnv copies of F, where v = |V (F)|. Proof. By the definition of π(F), we can find an integer m such that ex(m0 , F) n0 m. Assume the n-vertex k-graph G has (π(F) + ) n k edges. We use T to denote the number of pairs (e, M), where M ∈ V (G) m and e ∈ G[M]. On the one hand, we have T = X e∈E(G) n − k m − k = e(G) n − k m − k = (π(F) + ) n k n − k m − k = (π(F) + ) n m m k . On the other hand, if we let A = {M ∈ V (G) m : e(G[M]) > (π(F) + 2 ) m k }, then we get T = X M∈( V (G) m ) e(G[M]) = X M∈A e(G[M])+ X M /∈A e(G[M]) ≤ |A| m k +( n m −|A|)(π(F)+ 2 ) m k . The above two inequalities indicate that (π(F) + ) n m ≤ |A| + ( n m − |A|)(π(F) + 2 ). So |A| ≥ 2 n m /(1 − 2 − π(F)). Since each M ∈ A satisfies e(G[M]) > (π(F) + 2 ) m k > ex(m, F), we know G[M] has at least one copy of F. As each F can be contained in at most n−v m−v choices of M ⊂ A, we finally get the number of F-copies in G is at least |A| ( n−v m−v ) = 2 ( n m) (1− 2 −π(F))( n−v m−v ) = δnv . 6
3BlowupLemma and Erdos-Stone-Simonovits Theorem3.1BlowupLemmaGiven a k-graph F, the t-blowup F(t) is a k-graph obtained from F by replacing each E V(F) byan independent subset I(u) of size t and replacing every edge [ui, 2,.., us) e E(F) by a completek-partite k-graph I(ui), I(u2), ..,I(u). For example, the t-blowup of K, is K,(t) = T,(rt).Theorem 3.1 (Blowup Lemma).For any k-graph F and t ≥ 1, we have π(F(t)) = (F). Inother words, ex(n, F) ≤ex(n, F(t) ≤ex(n, F) +en for any t,e>0 and n ≥n(t,e).Proof. Let f = /V(F). First, clearly we have ex(n,F) ≤ ex(n, F(t)) since F F(t). Thenwe can assume that for sufficiently large n, there exist e > 0 and an F(t)-free k-graph G on nvertices, with e(G) > ex(n, F) +enk. By supersaturation lemma, G contains at least (n) copiesof F where $=(e,F).Next we define an auxiliary f-graph G* on V(G) where X e (°) is an edge of G* if and only ifG[X] contains a copy of F. So e(G*) ≥ = 2(nJ). Take an integer T such that n 》 T 》 t, f.As e(G*) = (nJ) > ex(n, KT:f), by hypergraph Kovari-Sos-Turan theorem, we see G* has atleast one copy of KT:f.There are f! possible ways to embed a copy of F in an edge of KT:f. Now we give f! colorsto the edges of KT:f. Notice that one color stands for one possible embedding. By pigeonholeprinciple, there is a color whose number of edges is at least > ex(uT, Kt:f). So Kr:f containsIa monochromatic copy of Kt:f.This copy of Kt:f gives a copy of F(t) in G.The chromatic number of a graph G, denoted by x(G), is the minimum integer k such thatV(G) can be partitioned into k independent sets.Fact 3.2. x(G) ≤ k 台 G is is k-partite.Fact 3.3. From the blowup lemma, for any m ≥1,1π(T(rm)) = π(Kr) = 13.2Erdos-Stone-SimonovitsTheoremTheorem 3.4 (Erdos-Stone). If x(F) = r, then (F) = r(K,) = 1 -Proof. There exists an integer m such that F T-(rm). So ex(n, F) ≤ ex(n,T,(rm)), implyingthat π(F) ≤π(T(rm) = π(K,) = 1 - -.For the lower bound, since x(F) = r, we see Tr-i(n)is F-free. Then ex(n, F) ≥ e(Tr-i(n). Combining them, we get11π(F) = π(Kr) = 1r-1x(F)-1IObviously, the above theorem has thefollowing versionTheorem 3.5 (Erds-Stone). For ang graph F and n, ex(n,F)=(1-x()- +o(1)() whereo(1) → 0 as n → +o0.7
3 Blowup Lemma and Erd˝os-Stone-Simonovits Theorem 3.1 Blowup Lemma Given a k-graph F, the t-blowup F(t) is a k-graph obtained from F by replacing each v ∈ V (F) by an independent subset I(v) of size t and replacing every edge {v1, v2, ., vk} ∈ E(F) by a complete k-partite k-graph I(v1), I(v2), ., I(vk). For example, the t-blowup of Kr is Kr(t) = Tr(rt). Theorem 3.1 (Blowup Lemma). For any k-graph F and t ≥ 1, we have π(F(t)) = π(F). In other words, ex(n, F) ≤ ex(n, F(t)) ≤ ex(n, F) + εnk for any t, ε > 0 and n ≥ n(t, ε). Proof. Let f = |V (F)|. First, clearly we have ex(n, F) ≤ ex(n, F(t)) since F ⊆ F(t). Then we can assume that for sufficiently large n, there exist ε > 0 and an F(t)-free k-graph G on n vertices, with e(G) > ex(n, F) + εnk . By supersaturation lemma, G contains at least δ n f copies of F where δ = δ(ε, F). Next we define an auxiliary f-graph G∗ on V (G) where X ∈ n f is an edge of G∗ if and only if G[X] contains a copy of F. So e(G∗ ) ≥ δnf f! = Ω(n f ). Take an integer T such that n T t, f. As e(G∗ ) = Ω(n f ) > ex(n, KT:f ), by hypergraph K¨ovari-S´os-Tur´an theorem, we see G∗ has at least one copy of KT:f . There are f! possible ways to embed a copy of F in an edge of KT:f . Now we give f! colors to the edges of KT:f . Notice that one color stands for one possible embedding. By pigeonhole principle, there is a color whose number of edges is at least T f f! > ex(vT, Kt:f ). So KT:f contains a monochromatic copy of Kt:f . This copy of Kt:f gives a copy of F(t) in G. The chromatic number of a graph G, denoted by χ(G), is the minimum integer k such that V (G) can be partitioned into k independent sets. Fact 3.2. χ(G) ≤ k ⇔ G is is k-partite. Fact 3.3. From the blowup lemma, for any m ≥ 1, π(Tr(rm)) = π(Kr) = 1 − 1 r − 1 . 3.2 Erd˝os-Stone-Simonovits Theorem Theorem 3.4 (Erd˝os-Stone). If χ(F) = r, then π(F) = π(Kr) = 1 − 1 r−1 . Proof. There exists an integer m such that F ⊆ Tr(rm). So ex(n, F) ≤ ex(n, Tr(rm)), implying that π(F) ≤ π(Tr(rm)) = π(Kr) = 1 − 1 r−1 . For the lower bound, since χ(F) = r, we see Tr−1(n) is F-free. Then ex(n, F) ≥ e(Tr−1(n)). Combining them, we get π(F) = π(Kr) = 1 − 1 r − 1 = 1 − 1 χ(F) − 1 Obviously, the above theorem has the following version. Theorem 3.5 (Erd˝os-Stone). For any graph F and n, ex(n, F) = (1 − 1 χ(F)−1 + o(1)) n 2 where o(1) → 0 as n → +∞. 7
Let F be a family of graphs. Let the chromatic number x(F) =minFeF x(F)Theorem3.6 (Erdos-Stone; observed by Simonovits).For any familyF of graphs,1π(F) = 1 -x(F)-1Let us see some easy observations.1. For any family F of graphs, r(F) E [0, , ,.., ,..]2. For any graph F, ex(n, F) =(1 - x()- +o(1)(2). When x(F) = 2(ie. F is bipartte),this becomes ex(n, F) = o(n?2).The problem of finding ex(n,F) for bipartite graphs F is call degenerate Tuan problem.3.3Quantitative Version of Erdos-Stone-Simonovits TheoremErdos-Stone-Simonovits theorem says ex(n,T,(rm)) ≤ (1 -- +e)(n). That means for fixedm, e, it holds for large n. Now we consider the counterpart that for fixed n,e, how large m canbe?For convenience, let us define a functionm : ex(n, T,(rm) ≤ex(n, K,) +efr(n,)=ma)≤1 and f ~ g if limn-→f(n)For functions f, g, we write f ≤ g if limn-→+g(m)=1++00g(n)The Erdos-Renyi random graph G(n,p) for o ≤ p ≤ 1 is a graph on n vertices, where eachpair of vertices forms an edge with probability p, independently at random. In particular, G(n, )can be viewed as an equally distributed probability space which consists of all labeled n-vertexgraphs.Theorem 3.7 (upper bound proved by Bollobas-Erdos).log1/en≤f2(n,e)≤2log1/enProof. First consider the lower bound. Let m = logi/e n, so n-1/m = e. Thusen21)1/mm2-1/m+-1)nex(n, T2(2m)) = ex(n, Km,m) ≤2This proves log1/e n ≤ f2(n, e)Second, let t = 2log1/e n. To show f2(n,e) e(2) - 1. Itsuffices to construct a n-vertex Kt,t-free graph G with at least (2) - 1 edges. Consider Erdos-Renyi random graph G(n,e). Let X be the number of Kt,t in G(n,e). We have)et? e(2) - 1. Let G' be obtained from G by deleting one edge for eachcopy of Kt,t in G. Then G' is Kt,t-free with e(G') ≥ e(G) - X > e() - 1.8
Let F be a family of graphs. Let the chromatic number χ(F) = minF ∈F χ(F). Theorem 3.6 (Erd˝os-Stone; observed by Simonovits). For any family F of graphs, π(F) = 1 − 1 χ(F) − 1 . Let us see some easy observations. 1. For any family F of graphs, π(F) ∈ {0, 1 2 , 2 3 , ., r−1 r , .}. 2. For any graph F, ex(n, F) = (1 − 1 χ(F)−1 + o(1)) n 2 . When χ(F) = 2(i.e. F is bipartite), this becomes ex(n, F) = o(n 2 ). The problem of finding ex(n, F) for bipartite graphs F is call degenerate Tu´an problem. 3.3 Quantitative Version of Erd˝os-Stone-Simonovits Theorem Erd˝os-Stone-Simonovits theorem says ex(n, Tr(rm)) ≤ (1 − 1 r−1 + ε) n 2 . That means for fixed m, , it holds for large n. Now we consider the counterpart that for fixed n, ε, how large m can be? For convenience, let us define a function fr(n, ε) = max m : ex(n, Tr(rm)) ≤ ex(n, Kr) + ε n 2 − 1 . For functions f, g, we write f . g if limn→+∞ f(n) g(n) ≤ 1 and f ∼ g if limn→+∞ f(n) g(n) = 1. The Erd˝os-Reny´ı random graph G(n, p) for 0 ≤ p ≤ 1 is a graph on n vertices, where each pair of vertices forms an edge with probability p, independently at random. In particular, G(n, 1 2 ) can be viewed as an equally distributed probability space which consists of all labeled n-vertex graphs. Theorem 3.7 (upper bound proved by Bollob´as-Erd˝os). log1/ε n . f2(n, ε) . 2 log1/ε n. Proof. First consider the lower bound. Let m = log1/ε n, so n −1/m = ε. Thus ex(n, T2(2m)) = ex(n, Km,m) ≤ 1 2 (m − 1)1/mn 2−1/m + 1 2 (m − 1)n . εn2 2 . This proves log1/ε n . f2(n, ε). Second, let t = 2 log1/ε n. To show f2(n, ε) ε n 2 − 1. It suffices to construct a n-vertex Kt,t-free graph G with at least ε n 2 − 1 edges. Consider Erd˝osReny´ı random graph G(n, ε). Let X be the number of Kt,t in G(n, ε). We have E[X] = 1 2 n 2t 2t t ε t 2 ε n 2 − 1. Let G0 be obtained from G by deleting one edge for each copy of Kt,t in G. Then G0 is Kt,t-free with e(G0 ) ≥ e(G) − X > ε n 2 − 1. 8
The best general bound is used by Szemeredi's regularity lemma.Theorem 3.8 (Ishigami). For any r ≥2 and e = o(1), we have fr(n,e)~ f2(n,e). Thuslog1/en≤f.(n,e)≤2log1/enTheorem 3.9. For any e E (0, -r+1) where r is ficed,fr+1(n,e) ≤ f2 (C"1,r(r + 1)e)Proof. Assume not. Let t = f2(["l,r(r +1)e) + 1, then there exists a Kt,t-free []-vertex graphH with e(H) > r(r + 1)e(l) - 1. Let G be obtained from T,(n) by adding H into a part of size[]. We claim that G is T+i(r + 1)t)-free (prove it as an exercise). Thus we haveex(n,Tr+1(r + 1)t) ≥ e(G) =e(T,(n) + e(H) ≥ ex(n, Kr+1) + e(■By definition, fr+i(n,e) ≤t - 1 = f2(「"l,r(r + 1)e)
The best general bound is used by Szemeredi’s regularity lemma. Theorem 3.8 (Ishigami). For any r ≥ 2 and ε = o(1), we have fr(n, ε) ∼ f2(n, ε). Thus log1/ε n . fr(n, ε) . 2 log1/ε n. Theorem 3.9. For any ε ∈ (0, 1 r(r+1) ) where r is fixed, fr+1(n, ε) ≤ f2 d n r e, r(r + 1)ε . Proof. Assume not. Let t = f2(d n r e, r(r + 1)ε) + 1, then there exists a Kt,t-free d n r e-vertex graph H with e(H) > r(r + 1)ε d n r e 2 − 1. Let G be obtained from Tr(n) by adding H into a part of size d n r e. We claim that G is Tr+1((r + 1)t)-free (prove it as an exercise). Thus we have ex(n, Tr+1((r + 1)t)) ≥ e(G) = e(Tr(n)) + e(H) ≥ ex(n, Kr+1) + ε n 2 . By definition, fr+1(n, ε) ≤ t − 1 = f2(d n r e, r(r + 1)ε). 9
4Bondy-Simonovits Theorem on Even CyclesWe consider the upper bound of ex(n, C2k) for k ≥ 2 in this lecture.Theorem 4.1 (Bondy-Simonovits). There is a constant c > 0 such that for any k ≥2,ex(n, C2k)≤ckn1+1/k.Remark: The original proof gives c =100.First, let us give some remarks. The current best bound on ex(n, C2k) is as followsTheorem 4.2 (Bukh-Jiang, 2016).ex(n,C2k)≤80Vkl1ogk.nl+1/k+10k2nTheir proof heavily relies on A-B path Lemma.Conjecture 4.3 (Erdos-Simonovits).Fork≥2,ex(n, C2k) = 0(n1+1/k)This conjecture is known for k = 2,3, 5 only.In the following lecture, we will give three different proofs of Theorem 4.1. Let us get intothe first one by introducing the A-B path lemma.4.1TheFirst ProofTheorem 4.4 (A-B path Lemma). Let H be a graph consisting of a cycle with a chord, and let(A,B)be anon-trivial partition of V(H).Then for anyl </V(H)l,thereis an(A,B)-path oflength l in H, unless l is even and H is bipartite with the partition (A, B).The first proof of Theorem 4.1. Let the cycle C = (0,1,...,n - 1, 0) with chord (0,r). Wetake indices under modulo n. Denote x : V(H) -→ [0, 1) by x(i) = 1 for i E A and x(i) = 0 fori e B. Let P = (p e Zt : x(i) = x(i+p) holds for any i). So if l P, we can find an (A, B)-pathof length l using only the edges of C.It suffices for us to consider l E P. Let m E P be the smallest positive integer in P. Thenmn (exercise).For all withml,thereexists some (A,B)-path of length l.(Bythedefinitionofm.)Soweonlyneedto considerl=kmCase 1: Suppose the chord (0,r) satisfies that 1 < r ≤ m. Since m + (m +r -1), there issome -m < j ≤ 0 such that x(i) + x(j + m +r - 1) = x(j + km +r - 1). Consider the path- 1,...,j + km + r - 1). This is an (A, B)-path of length(j,j+1,...,0,r,r+1,....j+m+r-.km=l.Case 2: Suppose m<r< n-m. For -m≤j≤0, we define2 paths:Pj=(j,j+1,...,0,r,r-1,...,r-j-m+1) and Qi= (m+ j,m + j-1,...,0,r,r +1...,r-j-1). We see both pathshavelengthm(i) Suppose there is a j with -m ≤ j ≤ O such that P, or Q, is an (A, B)-path. Then we canextend it to an (A, B)-path of length km = l by adding a subpath of length m at a time.(ii) We may assume that P, and Qj are not (A, B)-paths for all -m ≤ j ≤ 0. Then we havex(i) = x(r-j-m+1), x(m+j) = x(r-j-1) for any -m ≤j≤0. So x(r-j+1) = x(r-j-1),for any -m ≤ j ≤ 0. That is x(i) = x(i + 2) for any i. Then for m = 2, we have 2|n and the10
4 Bondy-Simonovits Theorem on Even Cycles We consider the upper bound of ex(n, C2k) for k ≥ 2 in this lecture. Theorem 4.1 (Bondy-Simonovits). There is a constant c > 0 such that for any k ≥ 2, ex(n, C2k) ≤ ckn1+1/k . Remark: The original proof gives c = 100. First, let us give some remarks. The current best bound on ex(n, C2k) is as follows. Theorem 4.2 (Bukh-Jiang, 2016). ex(n, C2k) ≤ 80√ k log k · n 1+1/k + 10k 2n. Their proof heavily relies on A-B path Lemma. Conjecture 4.3 (Erd˝os-Simonovits). For k ≥ 2, ex(n, C2k) = Θ(n 1+1/k). This conjecture is known for k = 2, 3, 5 only. In the following lecture, we will give three different proofs of Theorem 4.1. Let us get into the first one by introducing the A-B path lemma. 4.1 The First Proof Theorem 4.4 (A-B path Lemma). Let H be a graph consisting of a cycle with a chord, and let (A, B) be a non-trivial partition of V (H). Then for any ` < |V (H)|, there is an (A, B)-path of length ` in H, unless ` is even and H is bipartite with the partition (A, B). The first proof of Theorem 4.1. Let the cycle C = (0, 1, . . . , n − 1, 0) with chord (0, r). We take indices under modulo n. Denote χ : V (H) → {0, 1} by χ(i) = 1 for i ∈ A and χ(i) = 0 for i ∈ B. Let P = {p ∈ Z + n : χ(i) = χ(i+p) holds for any i}. So if ` 6∈ P, we can find an (A, B)-path of length ` using only the edges of C. It suffices for us to consider ` ∈ P. Let m ∈ P be the smallest positive integer in P. Then m|n (exercise). For all ` with m - `, there exists some (A, B)-path of length `.(By the definition of m.) So we only need to consider ` = km. Case 1: Suppose the chord (0, r) satisfies that 1 < r ≤ m. Since m - (m + r − 1), there is some −m < j ≤ 0 such that χ(j) 6= χ(j + m + r − 1) = χ(j + km + r − 1). Consider the path (j, j + 1, . . . , 0, r, r + 1, . . . , j + m + r − 1, . . . , j + km + r − 1). This is an (A, B)-path of length km = `. Case 2: Suppose m < r < n− m. For −m ≤ j ≤ 0, we define 2 paths: Pj = (j, j + 1, . . . , 0, r, r − 1, . . . , r − j − m + 1) and Qj = (m + j, m + j − 1, . . . , 0, r, r + 1 . . . , r − j − 1). We see both paths have length m. (i) Suppose there is a j with −m ≤ j ≤ 0 such that Pj or Qj is an (A, B)-path. Then we can extend it to an (A, B)-path of length km = ` by adding a subpath of length m at a time. (ii) We may assume that Pj and Qj are not (A, B)-paths for all −m ≤ j ≤ 0. Then we have χ(j) = χ(r−j−m+1), χ(m+j) = χ(r−j−1) for any −m ≤ j ≤ 0. So χ(r−j+1) = χ(r−j−1), for any −m ≤ j ≤ 0. That is χ(i) = χ(i + 2) for any i. Then for m = 2, we have 2|n and the 10