کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4651922 | 1632582 | 2015 | 5 صفحه PDF | دانلود رایگان |
For a graph G, the k -colour Ramsey number Rk(G)Rk(G) is the least integer N such that every k -colouring of the edges of the complete graph KNKN contains a monochromatic copy of G . Bondy and Erdős conjectured that for an odd cycle CnCn on n>3n>3 vertices,Rk(Cn)=2k−1(n−1)+1.Rk(Cn)=2k−1(n−1)+1. This is known to hold when k=2k=2 and n>3n>3, and when k=3k=3 and n is large. We show that this conjecture holds asymptotically for k≥4k≥4, proving that for n odd,Rk(Cn)=2k−1n+o(n)asn→∞. The proof uses the regularity lemma to relate this problem in Ramsey theory to one in convex optimisation, allowing analytic methods to be exploited. Our analysis leads us to a new class of lower bound constructions for this problem, which naturally arise from perfect matchings in the k-dimensional hypercube. Progress towards a resolution of the conjecture for large n is also discussed.
Journal: Electronic Notes in Discrete Mathematics - Volume 49, November 2015, Pages 377–381