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)< (π(F)+ )(m)for any m' ≥ m. Let n > 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) < (π(F) + 2 ) m0 k for any m0 ≥ m. Let n > 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) <t, we need to prove ex(n, Kt,t) > 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?<n2tet?= (n2et)t.E[X] = Since et = e2logi/en = n-2, we see E[X] < 1. By average, there exists a graph G such thate(G) - X ≥ E[e(G) - X) > 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, ε) < t, we need to prove ex(n, Kt,t) > ε 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 < n2t ε t 2 = (n 2 ε t ) t . Since ε t = ε 2 log1/ε n = n −2 , we see E[X] < 1. By average, there exists a graph G such that e(G) − X ≥ E[e(G) − X] > ε 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