《离散数学》课程教学资源（英文讲义）极值组合数学 Extremal Combinatorics.pdf_P11-P15

vertices of C alternate between A and B. If the chord (O,r) is in the same part, we can checkthat H contains A-B paths of all possible lengths. Otherwise, the chord (O,r) is between A andB, then H is bipartite with the partition (A, B).ICase 3: n - m ≤ r < n - 1. This case is the same as Case 1.Proof of Theorem4.1.Wewill showex(n, C2k) ≤ 2knl+1/k + 6(k - 1)n.Let G be an n-vertex C2k-free graph with more than 2kn1+1/k + 6(k - 1)n edges. Then G hasa bipartite subgraph H' with e(H') > knl+1/k + 3(k - 1)n. Further, H' contains a bipartitesubgraph H with (H) > kn1/k + 3(k - 1). Let T be a breadth-first search tree (BFS tree) withroot r in H. Let L, = {u V(H) : d(r, u) = i) for i≥1. Since H is bipartite, each L, is stable.First we claim that e(Li-1, Li) ≤ (k - 1)(ILi-1l +[Lil) for each 1 ≤i ≤ k. Suppose not,e(Li-1, L) > (k-1)(/Li-1/+|Lil) for some i≥ 2. Then H(Li-1,L,) contains a subgraph H1 withs(H) ≥k. Then H, has an even cycle C of length at least 2k with a chord. Let A=V(C)nLi-1and B = V(C)n Li. Let T' be a subtree of T such that A V(T') and subject to this, T' isminimal. Let y be the root of T'. As T' is minimal, y has at least 2 branches. Let A' be thesubset of A formed by all vertices from one branch of T'. Then AIA'+ 0. Let B' = BU(A\A').Then (A',B') is not a bipartition of Hi.Let e be the distance between and y.Then l<i-1and 2k - 2i + 2l + 2 < 2k ≤ [V(C)l. By A-B path Lemma, we can find an (A',B')-path P oflength 2k-2i+2e+2inHi betweena EA'and bEB'.AsPiseven,bEA\A'.Let Pa,Pbe the unique paths in T' that connect y to a and b respectively. Then PU Pa U P is a cycle oflength 2k in H, a contradiction.Next we show that [Lil ≥ ni/k|Li-il for any i E []. We prove this by induction on i. Basecase i =1 is trivial since (H) > kn1/k +3(k - 1). For i≥ 2, we have(kn1/k + 3(k - 1)|Li-1l ≤ dH(u) = e(Li-2, Li-1) + e(Li-1, Li)VELi-≤ (k -1)(/Li-2/ +2|Li-1/ +|L;l) ≤ (-1)(3|Li-1/ +[Lil),ISo [L;| ≥ kn-|Li-1| ≥ nl/k[Li-il, as desired. Now we see |L/ ≥ n, a contradiction.4.2The Second ProofNext, we move into the second proof of Theorem 4.1.Lemma 4.5(Lemma 2.6 in[1l).Let Hbe a connected graph where each edge is colored bycolor1 or color 2. Suppose that there is at least one edge of each color.If the number of edges of color1 is at least (p + 1)/V(H)l, then there erists a path of length p in H, whose first edge is coloredby color 2 and all other edges are colored by color 1.IProof. Exercise.The second proof of Theorem 4.1.This is gave by Jiang-Ma in [1].We aim to showex(n,C2k)≤8kn1+1/k+24kn.11

vertices of C alternate between A and B. If the chord (0, r) is in the same part, we can check that H contains A-B paths of all possible lengths. Otherwise, the chord (0, r) is between A and B, then H is bipartite with the partition (A, B). Case 3: n − m ≤ r < n − 1. This case is the same as Case 1. Proof of Theorem 4.1. We will show ex(n, C2k) ≤ 2kn1+1/k + 6(k − 1)n. Let G be an n-vertex C2k-free graph with more than 2kn1+1/k + 6(k − 1)n edges. Then G has a bipartite subgraph H0 with e(H0 ) > kn1+1/k + 3(k − 1)n. Further, H0 contains a bipartite subgraph H with δ(H) > kn1/k + 3(k − 1). Let T be a breadth-first search tree (BFS tree) with root x in H. Let Li = {u ∈ V (H) : dH(x, u) = i} for i ≥ 1. Since H is bipartite, each Li is stable. First we claim that e(Li−1, Li) ≤ (k − 1)(|Li−1| + |Li |) for each 1 ≤ i ≤ k. Suppose not, e(Li−1, Li) > (k −1)(|Li−1|+|Li |) for some i ≥ 2. Then H(Li−1, Li) contains a subgraph H1 with δ(H1) ≥ k. Then H1 has an even cycle C of length at least 2k with a chord. Let A = V (C)∩Li−1 and B = V (C) ∩ Li . Let T 0 be a subtree of T such that A ⊆ V (T 0 ) and subject to this, T 0 is minimal. Let y be the root of T 0 . As T 0 is minimal, y has at least 2 branches. Let A0 be the subset of A formed by all vertices from one branch of T 0 . Then A \ A0 6= ∅. Let B0 = B ∪(A \ A0 ). Then (A0 , B0 ) is not a bipartition of H1. Let ` be the distance between x and y. Then ` < i − 1 and 2k − 2i + 2` + 2 < 2k ≤ |V (C)|. By A-B path Lemma, we can find an (A0 , B0 )-path P of length 2k − 2i + 2` + 2 in H1 between a ∈ A0 and b ∈ B0 . As |P| is even, b ∈ A \ A0 . Let Pa, Pb be the unique paths in T 0 that connect y to a and b respectively. Then P ∪ Pa ∪ Pb is a cycle of length 2k in H, a contradiction. Next we show that |Li | ≥ n 1/k|Li−1| for any i ∈ [k]. We prove this by induction on i. Base case i = 1 is trivial since δ(H) > kn1/k + 3(k − 1). For i ≥ 2, we have (kn1/k + 3(k − 1))|Li−1| ≤ X v∈Li−1 dH(v) = e(Li−2, Li−1) + e(Li−1, Li) ≤ (k − 1)(|Li−2| + 2|Li−1| + |Li |) ≤ (k − 1)(3|Li−1| + |Li |). So |Li | ≥ kn1/k k−1 |Li−1| ≥ n 1/k|Li−1|, as desired. Now we see |Lk| ≥ n, a contradiction. 4.2 The Second Proof Next, we move into the second proof of Theorem 4.1. Lemma 4.5 (Lemma 2.6 in [1]). Let H be a connected graph where each edge is colored by color 1 or color 2. Suppose that there is at least one edge of each color. If the number of edges of color 1 is at least (p + 1)|V (H)|, then there exists a path of length p in H, whose first edge is colored by color 2 and all other edges are colored by color 1. Proof. Exercise. The second proof of Theorem 4.1. This is gave by Jiang-Ma in [1]. We aim to show ex(n, C2k) ≤ 8kn1+1/k + 24kn. 11

Let G be a n-vertex C2k-free graph with more than 8knI+1/k +24kn edges. Then G has a bipartitesubgraph H' with e(H') > 4kni+1/k + 12kn. Further, H' contains a bipartite subgraph H with(H) > 4kn1/k +12k. Similarly, let T be a breadth-first search tree (BFS tree) with root in H.Let L, = [u E V(H)|dh(r, u) = i) for i ≥ 1. Since H is bipartite, each L, is stable.First we claim that e(Li-1,Li) ≤ 4k(ILi-il + [Lil) for each 1 ≤ i ≤ k. Suppose not,e(Li-1, L;) > 4k((Li-1/+[L;l) for some i≥ 2. Take a connected component H* with d(H*) ≥ 8kin H(Li-1, Li). Let T' be a subtree of T with V(H*)n Li-1 C V(T'), and subject to this, T' isminimal.Let Xbethe subset ofhichfornnedbyallverticesfromonebranchofT.Let Y = (V(H*)nLi-i)color 1 if it has an end inX and bycolor 2 if it has anmber of edges with color 1 is atleast2k/V(H*)l.ByLemma1whose first edge islengthatleast2kcolored by color 2 and all otheowecanfindconsecutiveevercyclesof length2t+2,2tthedistancebetweenLi-1andtherootof T'. Sincet<i<k,thereoflength2k.ntradictiNext, we claim that [L;|≥ranyi[k].Weprovethisbyinductiononi.Basecase i=1 holds as (H) >4knl/k+12k. For i>2, we have(4kn/k + 12k)/Li-il ≤ dH(u) =e(Li-2, Li-1) +e(Li-1, L)DEL≤ 4k(/Li-2/ +2|Li-1/ +[Lil) ≤4k(3|Li-1/ +[Lil),then [L;| ≥ n//k|Li-il. Finally, we get [L| ≥ n, a contradiction.■4.3The Third ProofIt is due to Oliver Janzer in [2].For graphs H and G, we write hom(H,G) for the number of homomorphisms Φ : V(H) →V(G) such that if ry E E(H) then (r)(y) E E(G).Definition 4.6. A homomorphic copy of C2e is a tuple (r1,..,2e) e V(G)2 such that ri22,.., 22eri EE(G).Lemma 4.7.Let l≥2and G be a properly edge-colored graph.Then the number of homomorphiccopies of C2e which are NOT rainbow is at most 16e(e(G)hom(C2e-2, G)hom(C2e, G))Proof. It suffices to prove that the number of (ri,..2e) with 172, 273,.., 2e1 E E(G) suchthat c(ri2) = c(riri+1) for some 2≤i≤l +1 is at most8 ((G)hom(C2e-2, G)hom(C2e, G)For s ≥ 1, let as be the number of walks of length l - 1 in G whose endpoints y and z satisfy2s-1 ≤homy,(Pe-1,G) ≤ 2°.12

Let G be a n-vertex C2k-free graph with more than 8kn1+1/k+24kn edges. Then G has a bipartite subgraph H0 with e(H0 ) > 4kn1+1/k + 12kn. Further, H0 contains a bipartite subgraph H with δ(H) > 4kn1/k + 12k. Similarly, let T be a breadth-first search tree (BFS tree) with root x in H. Let Li = {u ∈ V (H)|dH(x, u) = i} for i ≥ 1. Since H is bipartite, each Li is stable. First we claim that e(Li−1, Li) ≤ 4k(|Li−1| + |Li |) for each 1 ≤ i ≤ k. Suppose not, e(Li−1, Li) > 4k(|Li−1| + |Li |) for some i ≥ 2. Take a connected component H∗ with d(H∗ ) ≥ 8k in H(Li−1, Li). Let T 0 be a subtree of T with V (H∗ ) ∩ Li−1 ⊆ V (T 0 ), and subject to this, T 0 is minimal. Let X be the subset of V (H∗ ) ∩ Li−1 which formed by all vertices from one branch of T 0 . Let Y = (V (H∗ ) ∩ Li−1) \ X. Color all edges in H∗ by color 1 if it has an end in X and by color 2 if it has an end in Y. Then we can assume that the number of edges with color 1 is at least 2k|V (H∗ )|. By Lemma 4.5, there is a path P of length at least 2k − 1 whose first edge is colored by color 2 and all other edges are colored by color 1. So we can find consecutive even cycles of length 2t + 2, 2t + 4, . . . , 2t + 2k − 2 where t is the distance between Li−1 and the root of T 0 . Since t < i ≤ k, there is a cycle of length 2k, a contradiction. Next, we claim that |Li | ≥ n 1/k|Li−1| for any i ∈ [k]. We prove this by induction on i. Base case i = 1 holds as δ(H) > 4kn1/k + 12k. For i ≥ 2, we have (4kn1/k + 12k)|Li−1| ≤ X v∈Li−1 dH(v) = e(Li−2, Li−1) + e(Li−1, Li) ≤ 4k(|Li−2| + 2|Li−1| + |Li |) ≤ 4k(3|Li−1| + |Li |), then |Li | ≥ n 1/k|Li−1|. Finally, we get |Lk| ≥ n, a contradiction. 4.3 The Third Proof It is due to Oliver Janzer in [2]. For graphs H and G, we write hom(H, G) for the number of homomorphisms φ : V (H) → V (G) such that if xy ∈ E(H) then φ(x)φ(y) ∈ E(G). Definition 4.6. A homomorphic copy of C2` is a tuple (x1, ., x2`) ∈ V (G) 2` such that x1x2, ., x2`x1 ∈ E(G). Lemma 4.7. Let ` ≥ 2 and G be a properly edge-colored graph. Then the number of homomorphic copies of C2` which are NOT rainbow is at most 16` `∆(G)hom(C2`−2, G)hom(C2` , G) 1 2 . Proof. It suffices to prove that the number of (x1, ., x2`) with x1x2, x2x3, ., x2`x1 ∈ E(G) such that c(x1x2) = c(xixi+1) for some 2 ≤ i ≤ ` + 1 is at most 8l l∆(G)hom(C2`−2, G)hom(C2` , G) 1 2 . For s ≥ 1, let αs be the number of walks of length ` − 1 in G whose endpoints y and z satisfy 2 s−1 ≤ homy,z(P`−1, G) ≤ 2 s . 12

Proof.Let lbe the smallest positive integer satisfyinghom(C2e,G) ≥28lk3en△(G)Sincehom(C2, G) = 2e(G) ≤ n△(G),we have2≤l≤k.Note thathom(C21-2,G) <28(l-1);3(=-1)n△(G)-1 ≤hom(C2v;)hom(C21, G)28k3△(G)28(3△(G)By Lemma 4.7, the number of homomorphic C2e in G which are NOT rainbow is at most16e(e(G)hom(C2l-2, G)hom(C2e, G))*< hom(C2e, G)IHence, there is a homomorphic copy of C2e in G which is a rainbow cycle.Definition 4.9.An injectively homomorphic C2e is a homomorphic copy(1,.., 2e)of C2e,suchthat all vertices ri are distinct.Lemma 4.10. Let l ≥2 be a positive integer and let G be a graph. Then the number of homo-morphic, but not injective copies of C2e in G is at most16e(e(G)hom(C2e-2, G) hom(C2e, G) Proof. The proof is almost identical to the proof of Lemma 4.7.The only difference is thatinstead of bounding those homomorphic copies (r1,..,r2i) with c(rir2) = c(riti+1) for someI2≤i≤l +1. All details go through exactly the same way.Lemma 4.11.LetH be a bipartite graph and suppose that it does NOT contain a non-emptysubgraph with minimum degree at least d. Then the largest eigenvalue of H is at most 2Vd(H)Lemma 4.12. Let H be a bipartite graph with parts Y and Z. Suppose that H does NOT containa non-empty subgraph with minimum degree at least d.Then there erist bipartite graphs Hi,H2both with parts Y and Z such that E(H)is the disjoint union of E(Hi)and E(H2), every verterin Y has degree less than d in Hi and every verter in Z has degree less than d in H2.Proof.Since H has minimum degree less than d, there is a vertex u in H which has degree lessthan d. If u e Y, let every edge in H of the form u belong to Hi, otherwise let every edge ofthe form uu belong to H2. Set H' = H - u.Since H' has minimum degree less than d, there is a vertex u' in H'which has degree less thand. If a' e Y, let every edge in H' of the form u'u belong to Hi, otherwise let every edge of theformuubelongtoH2.SetH"=H-u.Continue this procedure until all edges are placed in Hi or H2.It is easy to see that these graphsIare suitable.14

Proof. Let ` be the smallest positive integer satisfying hom(C2` , G) ≥ 2 8` k 3`n∆(G) ` . Since hom(C2, G) = 2e(G) ≤ n∆(G), we have 2 ≤ ` ≤ k. Note that hom(C2`−2, G) < 2 8(`−1)k 3(`−1)n∆(G) `−1 ≤ hom(C2` , G) 2 8k 3∆(G) ≤ hom(C2` , G) 2 8` 3∆(G) . By Lemma 4.7, the number of homomorphic C2` in G which are NOT rainbow is at most 16` `∆(G)hom(C2`−2, G)hom(C2` , G) 1 2 < hom(C2` , G). Hence, there is a homomorphic copy of C2` in G which is a rainbow cycle. Definition 4.9. An injectively homomorphic C2` is a homomorphic copy (x1, ., x2`) of C2` , such that all vertices xi are distinct. Lemma 4.10. Let ` ≥ 2 be a positive integer and let G be a graph. Then the number of homomorphic, but not injective copies of C2` in G is at most 16` `∆(G)hom(C2`−2, G)hom(C2` , G) 1 2 . Proof. The proof is almost identical to the proof of Lemma 4.7. The only difference is that instead of bounding those homomorphic copies (x1, ., x2l) with c(x1x2) = c(xixi+1) for some 2 ≤ i ≤ ` + 1. All details go through exactly the same way. Lemma 4.11. Let H be a bipartite graph and suppose that it does NOT contain a non-empty subgraph with minimum degree at least d. Then the largest eigenvalue of H is at most 2 p d∆(H). Lemma 4.12. Let H be a bipartite graph with parts Y and Z. Suppose that H does NOT contain a non-empty subgraph with minimum degree at least d. Then there exist bipartite graphs H1, H2 both with parts Y and Z such that E(H) is the disjoint union of E(H1) and E(H2), every vertex in Y has degree less than d in H1 and every vertex in Z has degree less than d in H2. Proof. Since H has minimum degree less than d, there is a vertex u in H which has degree less than d. If u ∈ Y , let every edge in H of the form uv belong to H1, otherwise let every edge of the form uv belong to H2. Set H0 = H − u. Since H0 has minimum degree less than d, there is a vertex u 0 in H0 which has degree less than d. If u 0 ∈ Y , let every edge in H0 of the form u 0v belong to H1, otherwise let every edge of the form u 0v belong to H2. Set H00 = H0 − u 0 . Continue this procedure until all edges are placed in H1 or H2. It is easy to see that these graphs are suitable. 14

Lemma 4.13. Let H be a bipartite graph with parts Y and Z so that every vertex in Y has degree at most D1 and every vertex in Z has degree at most D2. Then the largest eigenvalue of H is at most √ D1D2. Proof. Exercise. Lemma 4.14. Let A and B be symmetric real matrices with largest eigenvalues λ and µ. Then the largest eigenvalue of A + B is at most λ + µ. Proof. Exercise. Proof of Lemma 4.11. Define graphs H1 and H2 as in Lemma 4.12. By Lemma 4.13, both H1 and H2 have largest eigenvalue at most p d∆(H). Hence, by Lemma 4.14, the largest eigenvalue of H is at most 2p d∆(H). Lemma 4.15. Let H be a bipartite graph with parts Y and Z. Let f : Y → R be a function and let g(z) = P y∈NH(z) f(y) for every z ∈ Z. Suppose that H does not contain a non-empty subgraph with minimum degree at least d. Then X y∈Y f 2 (y) ≥ 1 4d∆(H) X z∈Z g 2 (z). Proof. Let Y = {y1, y2, . . . , yt}, Z = {z1, z2, . . . , zk}, ~xT = (f(y1), f(y2), . . . , f(yt), 0, . . . , 0), and matrix A denote the adjacent matrix of H. Then we have (A~x) T = (0, . . . , 0, g(z1), g(z2), . . . , g(zk)). Assume that the maximum eigenvalue of A is λ, which implies that the maximum eigenvalue of A2 is λ 2 . Then we have ~xT AT A~x ~xT ~x ≤ max ~yT AT A~y ~yT ~y = λ 2 . . From Lemma 4.11 we know that λ 2 ≤ 4d∆(H). Since ~xT AT A~x ≤ λ 2~xT ~x, we have X y∈Y f 2 (y) ≥ 1 4d∆(H) X z∈Z g 2 (z). The next lemma is one of our key lemma. Lemma 4.16. Let k be a fixed positive integer and let G be a properly edge-colored non-empty graph on n vertices. Suppose that for some 2 ≤ l ≤ k we have hom(C2l , G) ≥ ck∆(G)hom(C2l−2, G). where ck = 218k 7 . Then G contains a rainbow C2k. Proof. Call a pair (x1, xl+1) of vertices nice if the number of rainbow injectively homomorphic copies of C2l of the form x1x2 . . . x2lx1 is greater than 1 − 1 ( 4k 2 ) homx1,xl+1 (C2l , G) = 1 − 1 ( 4k 2 ) (homx1,xl+1 (Pl , G))2 . Claim. If the pair (x1, xl) is nice, then there are at least 4k pairwise vertex-disjoint path between x1 and xl+1 such that no color appears more than once on these paths. 15