2026/03/22 by Ping Li, Yang Yang · 1 voice
Mathematics · #math.CO
arxiv published 2026/03/22 · arxiv updated 2026/06/10
For graphs F and G, F-multicolor Turán number of G, denoted by exF(n,G), is the maximum number of edge-disjoint copies of F in an n-vertex graph such that there is no copy of G whose edges come from distinct copies of F. We study this parameter mainly for cycle pairs and determine, up to asymptotic order, when exCk(n,C_ℓ) attains the three natural thresholds: the upper bound, the lower bound, and the n2-o(1) regime. In particular, for every odd k≥ 5 and every t≥ 1, where Ck(t) denotes the t-blow-up of Ck, we prove exCk(t)(n,Ck-2)=n2/(kt)2+o(n2), and establish a corresponding stability theorem. We further show that if F and G have the same odd girth k and there exist homomorphisms from both F and G to Ck, then exF(n,G)=n2-o(1); in particular, exCk(n,Ck)=n2-o(1) for odd k. In addition, we prove ex_C2k+1(n,C2ℓ+1)=O (n1+1/\lceil ℓ/k\rceil) for ℓ>k and exF(n,G)=O(ex(n,G)) for bipartite G. We particularly establish exC4(n,C4)=(√(2))/(8)n3/2+O(n), and give a sufficient condition under which the lower bound cannot be attained.