Proof. We randomly select two paths Pl and p2 from the set of homa1,il+(P,G) uniformly.Since one rainbow and injective homomorphic copies of C2u consists of two vertex-disjoint pathbetween ri and ri+1 such that no color appears more than once, then by the definition of nicepairP(pl and p2 either not vertex-disjoint or not rainbow)=1- P(Pl and p2 are vertex-disjoint and rainbow)1(5)Then we haveP(pl and p2 either not vertex-disjoint or not rainbow)P(claim not happen) <<1.So there exist 4k pairwise vertex-disjoint paths between 1 and i+1 such that no color appears-more than once on these paths.Let #denote the number of non-rainbow or non-injective homomorphic copies of Cau in G.ByLemma4.7and Lemma4.10, weknowthat≤321((G)hom(Ca,G)hom(Ca-2G)/23/hom(C21, G).And by definition of #, we know thatZ#≥-(homa1,21+1(P,G)2.(m1+) not nice (3)Since (homa1,1+1(P,G) = hom(C2L,G).(a1,+1)Then wehave3213/24k Z (homa,r:(P,G)? ≥(1-)hom(C21,G)SE2r(r,z)nicethom(Cal, G) ≥(G)hom(C2l-2, G)22k△(G) homa (C2t-2,G).2So there exist satisfiedZ(G) home(C21-2, G),(homar,≥(P,G)? ≥ (4.1)22EV(G) (r,z) nice216
Proof. We randomly select two paths P 1 and P 2 from the set of homx1,xl+1 (Pl , G) uniformly. Since one rainbow and injective homomorphic copies of C2l consists of two vertex-disjoint path between x1 and xl+1 such that no color appears more than once, then by the definition of nice pair P(P 1 and P 2 either not vertex-disjoint or not rainbow) = 1 − P(P 1 and P 2 are vertex-disjoint and rainbow) < 1 4k 2 . Then we have P(claim not happen) < 4k 2 P(P 1 and P 2 either not vertex-disjoint or not rainbow) < 1. So there exist 4k pairwise vertex-disjoint paths between x1 and xl+1 such that no color appears more than once on these paths. Let # denote the number of non-rainbow or non-injective homomorphic copies of C2l in G. By Lemma 4.7 and Lemma 4.10, we know that # ≤ 32l(l∆(G)hom(C2l , G)hom(C2l−2, G))1/2 ≤ 32l 3/2 c 1/2 k hom(C2l , G). And by definition of #, we know that # ≥ X (x1,xl+1) not nice 1 4k 2 (homx1,xl+1 (Pl , G))2 . Since X (x1,xl+1) (homx1,xl+1 (Pl , G))2 = hom(C2L, G). Then we have X x X (x,z)nice (homx,xz (Pl , G))2 ≥ (1 − 4k 2 32l 3/2 c 1/2 k )hom(C2l , G) ≥ 1 2 hom(C2l , G) ≥ ck 2 ∆(G)hom(C2l−2, G) = ck 2 ∆(G) X x homx(C2l−2, G). So there exist x satisfied X z∈V (G) (x,z) nice (homx,z(Pl , G))2 ≥ ck 2 ∆(G) X x homx(C2l−2, G). (4.1) 16
Let Z = {z E V(G) : (r, z) is nice) and Y = V(G). Let H be the bipartite graph with part Zand Y incident by graph G (i.e. z y E E(H) with color r if and only if z y E E(G) with color r)Case 1. If H does not contain a non-empty subgraph with minimum degree at least 4k.Let f(y) = homry(Pi-1,G) for any y E Y andg(y) = f(y)= homry(P-i,G)= homry(P-1,G)= homr2(P,G).yEN(2)yENH(2)yENG(z)Then by Lemma 4.15, we know that11homa(Cal-2,G) = Zf(v) ≥ 16kA(H)Zg(2) ≥ 16kA(H)(homrz(P,G)?yEYZEZZEZwhich is contradiction to (4.1).Case 2. If H contains a non-empty subgraphH with minimum degree at least 4k.If we have a vertex-disjoint rainbow path 1r2...at in Hi with length t (t < 2k), since8(Hi) ≥ 4k > t, there exist an adjacent edge tt+1 of t with the different color to the path andIt+1 is distinct to i, then we get a vertex-disjoint rainbow path i...&tt+i in Hi with lengtht+1.Thus we can havea vertex-disjoint rainbowpath Piwith start pointzo and endpointzi inZof length2k-2l.By definition of Z and the Claim, there are more than 4k pairwise vertex-disjoint pathsbetween and zo with length l such that pairwise no color appears more than once. There areat most 2k-2l paths have same color to Pi and at most 2k - 2l paths have same vertex to PiSo there exists a path P2 is rainbow and vertex-disjoint to Pi.And there are at most 2k -l paths have same color to Pi UP2 and at most 2k -I paths havesame vertex to Pi U P2 So there exists a path P3 is rainbow and vertex-disjoint to Pi U P2, andweget arainbowC2k=PiUP,UP3.1Corollary 4.17. Let k be a fired positive integer and let G be a properly edge-colored non-emptygraph on n vertices.Suppose that for some2≤j≤kwe havehom(C2j, G) = w(n△(G).Then, for n sufficiently large, G contains a rainbow C2k.Proof. Choose L = w(1) such that hom(C2j, G) ≥ Lin((G)i. Let l be the smallest integersatisfying hom(C2e, G) ≥ L'n(△(G)).If l = 1 then hom(C2,G) = 2e(G) < Ln△(G) is contradiction, so 2 ≤ l ≤ j ≤ k. Since lis smallest, now we have hom(C2,G) ≥ L△(G)hom(C2e-2,G). By Theorem 4.16, G contains arainbowC2k.IDefinition 4.18. Graph G is K-almost regular if △(G) ≥ Ks(G),Lemma 4.19 (Jiang-Seiver).Let ,c be positive reals, where e < 1 and c > 1.Let n be apositive integer that is sufficiently large as a function of e.Let G be a graph on n vertices withe(G) ≥ cnl+e. Then G contains a K-almost regular subgraph G' on m ≥ n2 vertices such thate(G)≥答ml+e and K=20.21+±17
Let Z = {z ∈ V (G) : (x, z) is nice} and Y = V (G). Let H be the bipartite graph with part Z and Y incident by graph G (i.e. z y ∈ E(H) with color r if and only if z y ∈ E(G) with color r) . Case 1. If H does not contain a non-empty subgraph with minimum degree at least 4k. Let f(y) = homxy(Pl−1, G) for any y ∈ Y and g(y) = X y∈NH(z) f(y) = X y∈NH(z) homxy(Pl−1, G) = X y∈NG(z) homxy(Pl−1, G) = homxz(Pl , G). Then by Lemma 4.15, we know that homx(C2l−2, G) = X y∈Y f 2 (y) ≥ 1 16k∆(H) X z∈Z g 2 (z) ≥ 1 16k∆(H) X z∈Z (homxz(Pl , G))2 , which is contradiction to (4.1). Case 2. If H contains a non-empty subgraphH1 with minimum degree at least 4k. If we have a vertex-disjoint rainbow path x1x2 . . . xt in H1 with length t (t < 2k), since δ(H1) ≥ 4k > t, there exist an adjacent edge xtxt+1 of xt with the different color to the path and xt+1 is distinct to xi , then we get a vertex-disjoint rainbow path x1 . . . xtxt+1 in H1 with length t + 1. Thus we can have a vertex-disjoint rainbow path P1 with start pointz0 and endpointz1 in Z of length 2k − 2`. By definition of Z and the Claim, there are more than 4k pairwise vertex-disjoint paths between x and z0 with length ` such that pairwise no color appears more than once. There are at most 2k − 2` paths have same color to P1 and at most 2k − 2l paths have same vertex to P1. So there exists a path P2 is rainbow and vertex-disjoint to P1. And there are at most 2k − l paths have same color to P1 ∪ P2 and at most 2k − l paths have same vertex to P1 ∪ P2 So there exists a path P3 is rainbow and vertex-disjoint to P1 ∪ P2, and we get a rainbow C2k = P1 ∪ P2 ∪ P3. Corollary 4.17. 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 ≤ j ≤ k we have hom(C2j , G) = ω(n∆(G) j ). Then, for n sufficiently large, G contains a rainbow C2k. Proof. Choose L = ω(1) such that hom(C2j , G) ≥ L jn(∆(G))j . Let ` be the smallest integer satisfying hom(C2` , G) ≥ L `n(∆(G))` . If ` = 1 then hom(C2, G) = 2e(G) < Ln∆(G) is contradiction, so 2 ≤ ` ≤ j ≤ k. Since ` is smallest, now we have hom(C2, G) ≥ L∆(G)hom(C2`−2, G). By Theorem 4.16, G contains a rainbow C2k. Definition 4.18. Graph G is K-almost regular if ∆(G) ≥ Kδ(G). Lemma 4.19 (Jiang-Seiver). Let , c be positive reals, where < 1 and c ≥ 1. Let n be a positive integer that is sufficiently large as a function of . Let G be a graph on n vertices with e(G) ≥ cn1+ . Then G contains a K-almost regular subgraph G0 on m ≥ n − 2 2+2 vertices such that e(G0 ) ≥ 2c 5 m1+ and K = 20 · 2 1+ 1 2 . 17
Definition 4.20. The rainbow Turan number ex*(n,H) is the macimum edges in a properlyedge-colored graph onn vertices which doesn't have rainbow H as a subgraph.Remark 4.21.Since a H-free graph must be a rainbow H-free graph, then we have ex*(n,H)>ex(n, H).Theorem 4.22 (Keevash-Mubayi-Sudakov-Verstraete).For all graph H, we have ex*(n,H)≤er(n, H) +o(n2).Theorem 4.23 (Main Theorem).Vk ≥ 2 ex*(n, C2k) = e(nl+).Proof. The lower bound was obtained by Keevash-Mubayi-Sudakov-Verstraete (Rainbow TuranProblems' TH1.3). We only prove the upper bound (i.e. ex*(n, C2k) ≤O(n1+).We assume that there exists n-vertex properly edge colored graph G with more than w(ni+)edges that does not have rainbow C2k as a subgraph.By Lemma 4.19 there exists a K-almost regular subgraph H in G on m vertices with morethan w(ml+) edges.From w(ml+) ≤ e(H) ≤ m△(H) ≤ mK8(H), we know 8(H) = w(m). Since C2ksatisfying Sidovenko-Conjecture, we havesk(hom(K2, H)2k _ (2e(G)2khom(C2k, H) ≥ ≥2k ≥mK)m(A(H)*= w(m(A(H).m2km2kwhichiscontradictiontoCorollary4.17-18
Definition 4.20. The rainbow Tur´an number ex∗ (n, H) is the maximum edges in a properly edge-colored graph on n vertices which doesn’t have rainbow H as a subgraph. Remark 4.21. Since a H-free graph must be a rainbow H-free graph, then we have ex∗ (n, H) ≥ ex(n, H). Theorem 4.22 (Keevash-Mubayi-Sudakov-Verstra¨ete). For all graph H, we have ex∗ (n, H) ≤ ex(n, H) + o(n 2 ). Theorem 4.23 (Main Theorem). ∀k ≥ 2 ex∗ (n, C2k) = Θ(n 1+ 1 k ). Proof. The lower bound was obtained by Keevash-Mubayi-Sudakov-Verstra¨ete (Rainbow Tur´an Problems’ TH1.3). We only prove the upper bound (i.e. ex∗ (n, C2k) ≤ O(n 1+ 1 k )). We assume that there exists n-vertex properly edge colored graph G with more than ω(n 1+ 1 k ) edges that does not have rainbow C2k as a subgraph. By Lemma 4.19 there exists a K-almost regular subgraph H in G on m vertices with more than ω( 2c 5 m1+ 1 k ) edges. From ω( 2c 5 m1+ 1 k ) ≤ e(H) ≤ m∆(H) ≤ mKδ(H), we know δ(H) = ω(m 1 k ). Since C2k satisfying Sidovenko-Conjecture, we have hom(C2k, H) ≥ (hom(K2, H))2k m2k = (2e(G))2k m2k ≥ δ 2k ≥ ( δ k mKk )m(∆(H))k = ω(m(∆(H))k ). which is contradiction to Corollary 4.17. 18
5Even-cycle-freeSubgraphsoftheHypercubeThe n-dimensional hypercube, Qn, is the graph whose vertex set is the family [0, 1jn and whoseedgesetisthesetof pairsthatdifferinexactlyonecoordinateHereare some observations on Qn as follows:(i) Qn is an n-regular graph with 2n vertices and n2n-1 edges.(i) Each vertex can also be defined by some subset S[n] as follows:Vi:1≤i≤n,Tl,iesus(i) =o,its(ii) According to the definition above, we can label each vertex of Qn with all subsets of [nl tget a layered structure of Qn: serving the families of subsets , (l), ... , (ll), (n) aslayers respectively. For S e (ml) and Te (nl),STeE(Qn)= Ji-l=1.For graphs Q and P, let ex(Q,P) denote the generalized Turan number, i.e., the maxi-mum number of edges in a P-free subgraph of Q. In particular, the Turan number, ex(n, P) =ex(Kn,P).Let c2(n) = (co.Can) = ex(OnCa) and c2e =, lim,C2e(n).n-2n-1e(Qn)Note that c2e exists. (Homework. Hints: Only need to verify that c2e(n) is a non-increasingand bounded function of n.) The following conjecture of Erdos is still open.Conjecture 5.1 (Erdos). C4 =.Erdos also asked if ex(Qn, Cze) = o(n . 2") for l > 2, i.e., whether o(n 2") edges in a subgraphof Qn would imply the existence of a cycle C2e for l > 2.Here are some known results as follows:. (Thomason-Wagner) c4 ≤ 0.6226..(Brass-Harborth-Nienborg) c4(n)≥(1 + 0) for n ≥ 9..(Conder-Lu) For C6, ≤ c6< 0.3941, due to Conder and Lu, respectively· (Chung) For l ≥ 2, C4e(n) ≤ cn-+.Next, we give the result to all c4e+2 for e≥3byFiuiredi and OzkahyaTheorem 5.2 (Firedi-Ozkahya). For l ≥ 3, then[ O(n-2),l e[3,5, 7],C4e+2(n) =(0(n-+ 1(-1),otherwise.i.e., C4l+2= 0.Combinethe known results and 5.2, we see that:le[2,3],C2l>0,C2 = 0, l E [4] U [6, 7,8, .-]It is still open to consider if cio = O or not. We will give two proofs about c2e for l E [4] U[6, 7, 8, ...]: One is proved by Furedi and Ozkahya, another is by Conlon.19
5 Even-cycle-free Subgraphs of the Hypercube The n-dimensional hypercube, Qn, is the graph whose vertex set is the family {0, 1} n and whose edge set is the set of pairs that differ in exactly one coordinate. Here are some observations on Qn as follows: (i) Qn is an n-regular graph with 2n vertices and n · 2 n−1 edges. (ii) Each vertex can also be defined by some subset S ⊆ [n] as follows: ∀i: 1 ≤ i ≤ n, ~vS(i) = 1, i ∈ S 0, i /∈ S . (iii) According to the definition above, we can label each vertex of Qn with all subsets of [n] to get a layered structure of Qn: serving the families of subsets ∅ , [n] 1 , · · · , [n] n−1 , [n] as layers respectively. For S ∈ [n] i and T ∈ [n] j , ST ∈ E(Qn) ⇒ |i − j| = 1. For graphs Q and P, let ex(Q, P) denote the generalized Tur´an number, i.e., the maximum number of edges in a P-free subgraph of Q. In particular, the Tur´an number, ex(n, P) = ex(Kn, P). Let c2`(n) = ex(Qn,C2`) e(Qn) = ex(Qn,C2`) n·2n−1 and c2` = lim n→+∞ c2`(n). Note that c2` exists. (Homework. Hints: Only need to verify that c2`(n) is a non-increasing and bounded function of n.) The following conjecture of Erd¨os is still open. Conjecture 5.1 ( Erd¨os). c4 = 1 2 . Erd¨os also asked if ex(Qn, C2`) = o(n· 2 n ) for ` > 2, i.e., whether o(n· 2 n ) edges in a subgraph of Qn would imply the existence of a cycle C2` for ` > 2. Here are some known results as follows: • (Thomason-Wagner) c4 ≤ 0.6226. • (Brass-Harborth-Nienborg) c4(n) ≥ 1 2 (1 + √ 0.9 n ) for n ≥ 9. • (Conder-Lu) For C6, 1 3 ≤ c6 < 0.3941, due to Conder and Lu, respectively. • (Chung) For ` ≥ 2, c4`(n) ≤ cn− 1 2 + 1 2` . Next, we give the result to all c4`+2 for ` ≥ 3 by F¨uredi and Ozkahya. ¨ Theorem 5.2 (F¨uredi-Ozkahya) ¨ . For ` ≥ 3, then c4`+2(n) = ( O(n − 1 2`+1 ), ` ∈ {3, 5, 7} , O(n − 1 16 + 1 16(`−1) ), otherwise. i.e., c4`+2 = 0. Combine the known results and 5.2, we see that: c2` > 0, ` ∈ {2, 3} , c2` = 0, ` ∈ {4} ∪ {6, 7, 8, .} . It is still open to consider if c10 = 0 or not. We will give two proofs about c2` for ` ∈ {4} ∪ {6, 7, 8, .}: One is proved by F¨uredi and Ozkahya, another is by Conlon. ¨ 19
5.1TheFirstProofofTheorem5.2byFiredi-OzkahyaFor k ≥3, let G be any C4k+2-free subgraph of Qn.Fix two integers a,b ≥2 such that 4a +4b =4k+4.Thenanycycleof length4acannot intersect acycleof length 4b ata single edge,otherwisetheirunion contains a Cak+2.Let N(G, P) denote the number of subgraphs of G that are isomorphic to P. For an edge ofQn: uv E E(Qn),we define the direction of uu, denoted by d(uv), to be the unique coordinatefrom [n] where the 0-1 vectors uand differ. Similarly, for a subgraph F of Qn,let D(F) :=[d(e) : eEE(F)).Lemma 5.3. Let C' and C"be cycles of length 4a and 4b of G, respectively,whose intersectioncontainsanedge.Then[D(C) n D(C")/ ≥ 2.Proof.Let ui, u2 be the endpoints of the common edge in the intersection of C'and C".By theprevious observation, there must be another vertex v common in C' and C". Because vg has atleast two coordinates that differs from either vi or v2, these two coordinates are also containedin the intersection of D(C) and D(C).IObservethat,foranycycleCoflengthC2einQn[D(C2e)/ ≤ l.Because the direction of each edge in C2e appears an even number of times on E(C2e). Based onthis observation, we can get the result directly as follows:N(G, C4a) ≤ N(Qn,C4a) ≤ 2n . O(n2a)Homework : Give a proof to explain the reason why the last equality holds.In the following, we obtain a better bound of N(G, C4a).Lemma 5.4.N(G,C4a)= e(G) -O(n2a-2)+ O(2nn2a-+),where G, a,b ≥2 are defined as before.Proof. Let C denote the family of all cycles of length 4a in G and let &o be the set of edgescontained in the cycles in C.Wepartition Co=& U&2,where &iis the collection of edges thatare contained in the intersection of a copy of C4a and a copy of C4b in G, and &2 := Co&i. Next.we count the cycles of length 4a in G over the edges in Co.By Lemma 5.3, every edge e E & is contained in O(n2a-2) members of C.(As the definitionof &i, for any cycle C4a contains e fixed, there exist a cycle C4b contains e.For e E &i,there areat most (2b) choices of the directions arranged to e, then according to Lemma5.3 about the fixedcycle C4a, there are at most (2g-2) choices of the directions to choose for the directions of alledges of C4a except e. Thus the edge e is contained in at most (2)(2a-2) = O(n2a-2) membersin C.)The subgraph induced by the edges in E2 does not contain a copy of C4b, implying that[&2l ≤ ex(Qn, C4b) ≤O(2"n+),20
5.1 The First Proof of Theorem 5.2 by F¨uredi -Ozkahya ¨ For k ≥ 3, let G be any C4k+2-free subgraph of Qn. Fix two integers a, b ≥ 2 such that 4a + 4b = 4k+4. Then any cycle of length 4a cannot intersect a cycle of length 4b at a single edge, otherwise their union contains a C4k+2. Let N(G, P) denote the number of subgraphs of G that are isomorphic to P. For an edge of Qn: uv ∈ E(Qn), we define the direction of uv, denoted by d(uv), to be the unique coordinate from [n] where the 0-1 vectors u and v differ. Similarly, for a subgraph F of Qn, let D(F) := {d(e) : e ∈ E(F)}. Lemma 5.3. Let C 0 and C 00 be cycles of length 4a and 4b of G, respectively, whose intersection contains an edge. Then D(C 0 ) ∩ D(C 00) ≥ 2. Proof. Let v1, v2 be the endpoints of the common edge in the intersection of C 0 and C 00. By the previous observation, there must be another vertex v3 common in C 0 and C 00. Because v3 has at least two coordinates that differs from either v1 or v2, these two coordinates are also contained in the intersection of D(C 0 ) and D(C 00). Observe that, for any cycle C of length C2` in Qn, |D(C2`)| ≤ `. Because the direction of each edge in C2` appears an even number of times on E(C2`). Based on this observation, we can get the result directly as follows: N(G, C4a) ≤ N(Qn, C4a) ≤ 2 n · O(n 2a ). Homework : Give a proof to explain the reason why the last equality holds. In the following, we obtain a better bound of N(G, C4a). Lemma 5.4. N(G, C4a) = e(G) · O(n 2a−2 ) + O(2nn 2a− 1 2 + 1 2b ), where G, a, b ≥ 2 are defined as before. Proof. Let C denote the family of all cycles of length 4a in G and let E0 be the set of edges contained in the cycles in C. We partition E0 = E1 ∪ E2, where E1 is the collection of edges that are contained in the intersection of a copy of C4a and a copy of C4b in G, and E2 := E0 \ E1. Next, we count the cycles of length 4a in G over the edges in E0. By Lemma 5.3, every edge e ∈ E1 is contained in O(n 2a−2 ) members of C.(As the definition of E1, for any cycle C4a contains e fixed, there exist a cycle C4b contains e. For e ∈ E1, there are at most 2b 2 choices of the directions arranged to e, then according to Lemma5.3 about the fixed cycle C4a, there are at most n 2a−2 choices of the directions to choose for the directions of all edges of C4a except e. Thus the edge e is contained in at most 2b 2 n 2a−2 = O(n 2a−2 ) members in C.) The subgraph induced by the edges in E2 does not contain a copy of C4b, implying that |E2| ≤ ex(Qn, C4b) ≤ O(2nn 1 2 + 1 2b ), 20