Generalized rainbow Turan numbers of odd cycles

被引:1
作者
Balogh, Jozsef [1 ,2 ]
Delcourt, Michelle [3 ]
Heath, Emily [4 ]
Li, Lina [5 ]
机构
[1] Univ Illinois, Dept Math, Urbana, IL 61801 USA
[2] Moscow Inst Phys & Technol, Moscow, Russia
[3] Ryerson Univ, Dept Math, Toronto, ON M5B 2K3, Canada
[4] Iowa State Univ, Dept Math, Ames, IA 50011 USA
[5] Univ Waterloo, Dept Combinator & Optimizat, Waterloo, ON N2L 3G1, Canada
基金
加拿大自然科学与工程研究理事会; 美国国家科学基金会;
关键词
Turan; Rainbow; Cycle;
D O I
10.1016/j.disc.2021.112663
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
Given graphs F and H, the generalized rainbow Turan number ex(n, F, rainbow -H) is the maximum number of copies of F in an n-vertex graph with a proper edge-coloring that contains no rainbow copy of H. B. Janzer determined the order of magnitude of ex(n, C-s, rainbow-C-t) for all s >= 4 and t >= 3, and a recent result of O. Janzer implied that ex(n, C3, rainbow-C-2k) = O(n(1+1/k)). We prove the corresponding upper bound for the remaining cases, showing that ex(n, C-3, rainbow-C2k+1) = O(n(1+1/k)). This matches the known lower bound for k even and is conjectured to be tight for k odd. (c) 2021 Elsevier B.V. All rights reserved.
引用
收藏
页数:4
相关论文
共 15 条
[1]   Many T copies in H-free graphs [J].
Alon, Noga ;
Shikhelman, Clara .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2016, 121 :146-172
[2]  
[Anonymous], 1962, MAGYAR TUD AKAD MAT
[3]  
BOLLOBAS B, 1976, MATH PROC CAMBRIDGE, V79, P19, DOI 10.1017/S0305004100052063
[4]   Pentagons vs. triangles [J].
Bollobas, Bela ;
Gyori, Ervin .
DISCRETE MATHEMATICS, 2008, 308 (19) :4332-4336
[5]  
Ergemlidze B, 2019, ELECTRON J COMB, V26
[6]  
Gerbner D., 2019, ARXIV191106642
[7]   Generalized Turan problems for even cycles [J].
Gerbner, Daniel ;
Gyori, Ervin ;
Methuku, Abhishek ;
Vizer, Mate .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2020, 145 :169-213
[8]   A Generalized Turan Problem and its Applications [J].
Gishboliner, Lior ;
Shapira, Asaf .
INTERNATIONAL MATHEMATICS RESEARCH NOTICES, 2020, 2020 (11) :3417-3452
[9]   Generalizations of the Ruzsa-Szemeredi and rainbow Turan problems for cliques [J].
Gowers, W. T. ;
Janzer, Barnabas .
COMBINATORICS PROBABILITY AND COMPUTING, 2021, 30 (04) :591-608
[10]   The Maximum Number of Triangles in C2k+1-Free Graphs [J].
Gyori, Ervin ;
Li, Hao .
COMBINATORICS PROBABILITY & COMPUTING, 2012, 21 (1-2) :187-191