Edges not in any monochromatic copy of a fixed graph

Abstract

For a sequence $(H_i{)}_{i=1}^k$ of graphs, let $\text{nim}(n;H_1,\dots ,H_k)$ denote the maximum number of edges not contained in any monochromatic copy of $H_i$ in colour $i$, for any colour $i$, over all $k$-edge-colourings of~$K_n$. When each $H_i$ is connected and non-bipartite, we introduce a variant of Ramsey number that determines the limit of $\text{nim}(n;H_1,\dots ,H_k)/\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ as $n\to \infty$ and prove the corresponding stability result. Furthermore, if each $H_i$ is what we call \emph{homomorphism-critical} (in particular if each $H_i$ is a clique), then we determine $\text{nim}(n;H_1,\dots ,H_k)$ exactly for all sufficiently large~$n$. The special case $\text{nim}(n;K_3,K_3,K_3)$ of our result answers a question of Ma. For bipartite graphs, we mainly concentrate on the two-colour symmetric case (i.e., when $k=2$ and $H_1=H_2$). It is trivial to see that $\text{nim}(n;H,H)$ is at least $\text{ex}(n,H)$, the maximum size of an $H$-free graph on $n$ vertices. Keevash and Sudakov showed that equality holds if $H$ is the $4$-cycle and $n$ is large; recently Ma extended their result to an infinite family of bipartite graphs. We provide a larger family of bipartite graphs for which $\text{nim}(n;H,H)=\text{ex}(n,H)$. For a general bipartite graph $H$, we show that $\text{nim}(n;H,H)$ is always within a constant additive error from $\text{ex}(n,H)$, i.e.,~$\text{nim}(n;H,H)=\text{ex}(n,H)+O_H(1)$.

24 pages, 3 figures