The Ramsey number of loose cycles versus cliques

被引:3
作者
Meroueh, Ares [1 ]
机构
[1] Ctr Math Sci, Dept Pure Math & Math Stat, Wilberforce Rd, Cambridge CB3 0WB, England
基金
英国工程与自然科学研究理事会;
关键词
loose cycle; Ramsey number; INDEPENDENCE NUMBER; HYPERGRAPHS; BOUNDS; GRAPH;
D O I
10.1002/jgt.22387
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
Let R(C-l(r), K-n(r)) be the Ramsey number of an r-uniform loose cycle of length l versus an r-uniform clique of order n. Kostochka et al. showed that for each fixed r >= 3, the order of magnitude of R(C-3(r), K-n(r)) is n(3/2) up to a polylogarithmic factor in n. They conjectured that for each r >= 3 we have R(C-5(r), K-n(r)) = O(n(5/4)). We prove that R(C-5(3), K-n(3)) = O(n(4/3)), and more generally for every l >= 3 that R(C-l(3), K-n(3)) = O(n(1+1/left perpendiclaur (1+1)/2 right perpendicular)). We also prove that for every l >= 5 and r >= 4, R(C-l(r), K-n(r)) = O(n(1+1/left perpendiclaur) l/2 (right perpendiclaur)) if l is odd, which improves upon the result of Collier-Cartaino et al. who proved that for every r >= 3 and l >= 4 we have R(C-l(r), K-n(r)) = O(n1+1/((left perpendiclaur) l/2 (right perpendiclaur) -1).
引用
收藏
页码:172 / 188
页数:17
相关论文
共 26 条
[1]   A NOTE ON RAMSEY NUMBERS [J].
AJTAI, M ;
KOMLOS, J ;
SZEMEREDI, E .
JOURNAL OF COMBINATORIAL THEORY SERIES A, 1980, 29 (03) :354-360
[2]  
Bohman T., 2013, Centro di Ricerca Matematica Ennio De Giorgi Series, P489
[3]   The early evolution of the H-free process [J].
Bohman, Tom ;
Keevash, Peter .
INVENTIONES MATHEMATICAE, 2010, 181 (02) :291-336
[4]   Pentagons vs. triangles [J].
Bollobas, Bela ;
Gyori, Ervin .
DISCRETE MATHEMATICS, 2008, 308 (19) :4332-4336
[5]   Asymptotic bounds for some bipartite graph: complete graph Ramsey numbers [J].
Caro, Y ;
Li, YS ;
Rousseau, CC ;
Zhang, YM .
DISCRETE MATHEMATICS, 2000, 220 (1-3) :51-56
[6]   Linear Turan Numbers of Linear Cycles and Cycle-Complete Ramsey Numbers [J].
Collier-Cartaino, Clayton ;
Graber, Nathan ;
Jiang, Tao .
COMBINATORICS PROBABILITY & COMPUTING, 2018, 27 (03) :358-386
[7]  
Erdos P., 1975, INFINITE FINITE SETS
[8]  
Erdos P., 1960, Journal of the London Mathematical Society, V35, P85
[9]  
Erds P., 1984, Proceedings of the International Congress of Mathematicians, V1, P51
[10]  
FizPontiveros G, 2013, TRIANGLE FREE PROCES