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?


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.