Strong Ramsey saturation for cycles

Strong Ramsey saturation for cycles

Tue, 22/05/2012
14:30 		Jozef Skokan (LSE) Combinatorial Theory Seminar Add to calendar L3
Strong Ramsey saturation for cycles
We call a graph $ H $ Ramsey-unsaturated if there is an edge in the complement of $ H $ such that the Ramsey number $ r(H) $ of $ H $ does not change upon adding it to $ H $. This notion was introduced by Balister, Lehel and Schelp who also showed that cycles (except for $ C_4 $) are Ramsey-unsaturated, and conjectured that, moreover, one may add any chord without changing the Ramsey number of the cycle $ C_n $, unless $ n $ is even and adding the chord creates an odd cycle. We prove this conjecture for large cycles by showing a stronger statement: If a graph $ H $ is obtained by adding a linear number of chords to a cycle $ C_n $, then $ r(H)=r(C_n) $, as long as the maximum degree of $ H $ is bounded, $ H $ is either bipartite (for even $ n $) or almost bipartite (for odd $ n $), and $ n $ is large. This motivates us to call cycles strongly Ramsey-unsaturated. Our proof uses the regularity method.