Premium
The Ramsey number of loose cycles versus cliques
Author(s) -
Méroueh Arès
Publication year - 2019
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22387
Subject(s) - mathematics , combinatorics , clique , ramsey's theorem , order (exchange) , discrete mathematics , graph , finance , economics
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 ∕ 2up 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 ∕ ⌊ ( l + 1 ) ∕ 2 ⌋) . We also prove that for every l ≥ 5 and r ≥ 4 , R ( C l r , K n r ) = O ( n 1 + 1 ∕ ⌊ l ∕ 2 ⌋) 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 ( n 1 + 1 ∕ ( ⌊ l ∕ 2 ⌋ − 1 )) .