Improved bounds on the multicolor Ramsey numbers of paths and even cycles Article Swipe
Related Concepts
Combinatorics
Ramsey's theorem
Mathematics
Upper and lower bounds
Monochromatic color
Graph
Matching (statistics)
Discrete mathematics
Physics
Statistics
Optics
Mathematical analysis
Charlotte Knierim
,
Pascal Su
·
YOU?
·
· 2019
· Open Access
·
· DOI: https://doi.org/10.3929/ethz-b-000338393
· OA: W3000382053
YOU?
·
· 2019
· Open Access
·
· DOI: https://doi.org/10.3929/ethz-b-000338393
· OA: W3000382053
We study the multicolor Ramsey numbers for paths and even cycles, Rk(Pn) and Rk(Cn), which are the smallest integers N such that every coloring of the complete graph KN has a monochromatic copy of Pn or Cn respectively. For a long time, Rk(Pn) has only been known to lie between (k−1+o(1))n and (k+o(1))n. A recent breakthrough by Sárközy and later improvement by Davies, Jenssen and Roberts give an upper bound of (k−14+o(1))n. We improve the upper bound to (k−12+o(1))n. Our approach uses structural insights in connected graphs without a large matching.
Related Topics
Finding more related topics…