2
$\begingroup$

Given $n$, consider the complete graph $K_{R(n)-1}$, where $R(n)$ is the diagonal Ramsey number.

So there exist $2$-colourings of the edges of $K_{R(n)-1}$ without a monochromatic copy of $K_n$.

However, in order to force such a colouring, it is perhaps not necessary to colour all the edges of $K_{R(n)-1}$: there may exist a proper subgraph $H$ on $R(n)-1$ vertices admitting a 2-colouring of its edges with the property that NO extension of the $2$-colouring to the whole of $K_{R(n)-1}$ will contain a monochromatic copy of $K_n$.

Let $M(n)$ denote the smallest possible size of such an $H$. What can be said about $M(n)$?

Clearly $M(n)\leq\binom{R(n)-1}{2}$, i.e. the number of edges of $K_{R(n)-1}$. Must we have equality there?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.