Number of edges needed for good colouring in Ramsey graph theory

150 Views Asked by At

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?