{
  "id": "1705.01997",
  "version": "v1",
  "published": "2017-05-04T20:05:08.000Z",
  "updated": "2017-05-04T20:05:08.000Z",
  "title": "Edges not in any monochromatic copy of a fixed graph",
  "authors": [
    "Hong Liu",
    "Oleg Pikhurko",
    "Maryam Sharifzadeh"
  ],
  "comment": "22 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "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)$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-05-04T20:05:08.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "monochromatic copy",
      "fixed graph",
      "general bipartite graph",
      "two-colour symmetric case",
      "constant additive error"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 22,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}