Edges not in any monochromatic copy of a fixed graph

Hong Liu, Oleg Pikhurko, Maryam Sharifzadeh

Published 2017-05-04Version 1

For a sequence $(H_i)_{i=1}^k$ of graphs, let $\mathrm{nim}(n;H_1,\ldots, H_k)$ denote the maximum number of edges not contained in any monochromatic copy of $H_i$ in 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 $\mathrm{nim}(n;H_1,\ldots, H_k)/{n\choose 2}$ as $n\to\infty$ and prove the corresponding stability result. Furthermore, if each $H_i$ is strongly-colour-critical (in particular if each $H_i$ is a clique), then we determine $\mathrm{nim}(n;H_1,\ldots, H_k)$ exactly for all sufficiently large $n$. The special case $\mathrm{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 $\mathrm{nim}(n;H,H)$ is at least $\mathrm{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 $\mathrm{nim}(n;H,H)=\mathrm{ex}(n,H)$. For a general bipartite graph $H$, we show that $\mathrm{nim}(n;H,H)$ is always within a constant additive error from $\mathrm{ex}(n,H)$, i.e., $\mathrm{nim}(n;H,H)= \mathrm{ex}(n,H)+O_H(1)$.