Cycle-complete Ramsey numbers

DOI10.1093/IMRN/RNZ119MaRDI QIDQ5005215zbMATH OpenOpenAlexFDO

Authors Peter Keevash, Eoin Long, J. Skokan

Publication date 9 August 2021

Published in IMRN. International Mathematics Research Notices (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1807.06376

zbMATH Keywords

cycle-complete Ramsey numbersgraph Ramsey numbers

Mathematics Subject Classification ID

Generalized Ramsey theory (05C55) Ramsey theory (05D10)

Abstract: The Ramsey number $r(C_{ell},K_n)$ is the smallest natural number $N$ such that every red/blue edge-colouring of a clique of order $N$ contains a red cycle of length $ell$ or a blue clique of order $n$. In 1978, ErdH{o}s, Faudree, Rousseau and Schelp conjectured that $r(C_{ell},K_n)=(ell-1)(n-1)+1$ for $ellgeqngeq3$ provided $(ell,n)eq(3,3)$. We prove that, for some absolute constant $Cge1$, we have $r(C_{ell},K_n)=(ell-1)(n-1)+1$ provided $ellgeqCfraclognloglogn$. Up to the value of $C$ this is tight since we also show that, for any $varepsilon>0$ and $n>n_0(varepsilon)$, we have $r(C_{ell},K_n)gg(ell-1)(n-1)+1$ for all $3leqellleq(1-varepsilon)fraclognloglogn$. This proves the conjecture of ErdH{o}s, Faudree, Rousseau and Schelp for large $ell$, a stronger form of the conjecture due to Nikiforov, and answers (up to multiplicative constants) two further questions of ErdH{o}s, Faudree, Rousseau and Schelp.

Recommendations

• The Cycle-Complete Graph Ramsey Numbers
• The Cycle-Complete Graph Ramsey Number r(C₅, K₇)
• All cycle‐complete graph Ramsey numbers r(C_m, K₆)
• The cycle-complete graph Ramsey number r(C₈,K₇)
• scientific article; zbMATH DE number 1556735

Cited in

(16)

• Generalised Ramsey numbers for two sets of cycles
• Tough Ramsey graphs without short cycles
• A note on multicolor Ramsey number of small odd cycles versus a large clique
• The Ramsey number of Fano plane versus tight path
• scientific article; zbMATH DE number 1556735 (Why is no real title available?)
• Linear Turán Numbers of Linear Cycles and Cycle-Complete Ramsey Numbers
• The Cycle-Complete Graph Ramsey Numbers
• Ramsey goodness of cycles
• Five Cycles are Highly Ramsey Infinite
• Cycles Are Strongly Ramsey-Unsaturated
• Ramsey numbers of cycles versus general graphs
• Ramsey Equivalence for Asymmetric Pairs of Graphs
• The Ramsey number of a long even cycle versus a star
• Transference for loose Hamilton cycles in random 3-uniform hypergraphs
• The Ramsey number for 4-uniform tight cycles
• Pancyclicity of Hamiltonian graphs

This page was built for publication: Cycle-complete Ramsey numbers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5005215)