{
  "id": "1010.5079",
  "version": "v1",
  "published": "2010-10-25T10:23:11.000Z",
  "updated": "2010-10-25T10:23:11.000Z",
  "title": "Ramsey-goodness -- and otherwise",
  "authors": [
    "Peter Allen",
    "Graham Brightwell",
    "Jozef Skokan"
  ],
  "comment": "34 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "A celebrated result of Chv\\'atal, R\\\"odl, Szemer\\'edi and Trotter states (in slightly weakened form) that, for every natural number $\\Delta$, there is a constant $r_\\Delta$ such that, for any connected $n$-vertex graph $G$ with maximum degree $\\Delta$, the Ramsey number $R(G,G)$ is at most $r_\\Delta n$, provided $n$ is sufficiently large. In 1987, Burr made a strong conjecture implying that one may take $r_\\Delta = \\Delta$. However, Graham, R\\\"odl and Ruci\\'nski showed, by taking $G$ to be a suitable expander graph, that necessarily $r_\\Delta > 2^{c\\Delta}$ for some constant $c>0$. We show that the use of expanders is essential: if we impose the additional restriction that the bandwidth of $G$ be at most some function $\\beta (n) = o(n)$, then $R(G,G) \\le (2\\chi(G)+4)n\\leq (2\\Delta+6)n$, i.e., $r_\\Delta = 2\\Delta +6$ suffices. On the other hand, we show that Burr's conjecture itself fails even for $P_n^k$, the $k$th power of a path $P_n$. Brandt showed that for any $c$, if $\\Delta$ is sufficiently large, there are connected $n$-vertex graphs $G$ with $\\Delta(G)\\leq\\Delta$ but $R(G,K_3)>cn$. We show that, given $\\Delta$ and $H$, there are $\\beta>0$ and $n_0$ such that, if $G$ is a connected graph on $n\\ge n_0$ vertices with maximum degree at most $\\Delta$ and bandwidth at most $\\beta n$, then we have $R(G,H)=(\\chi(H)-1)(n-1)+\\sigma(H)$, where $\\sigma(H)$ is the smallest size of any part in any $\\chi(H)$-partition of $H$. We also show that the same conclusion holds without any restriction on the maximum degree of $G$ if the bandwidth of $G$ is at most $\\epsilon(H) \\log n/\\log\\log n$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2010-10-25T10:23:11.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "maximum degree",
      "ramsey-goodness",
      "vertex graph",
      "sufficiently large",
      "additional restriction"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 34,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2010arXiv1010.5079A"
    }
  }
}