Date
Tue, 22 May 2012
Time
14:30 - 15:30
Location
L3
Speaker
Jozef Skokan
Organisation
LSE

We call a graph $H$ \emph{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 {\em

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 \emph{strongly} Ramsey-unsaturated.

Our proof uses the regularity method.

Please contact us with feedback and comments about this page. Last updated on 03 Apr 2022 01:32.