{
  "id": "1307.6327",
  "version": "v3",
  "published": "2013-07-24T08:31:23.000Z",
  "updated": "2014-12-12T13:03:44.000Z",
  "title": "Ramsey for complete graphs with dropped cliques",
  "authors": [
    "Jonathan Chappelon",
    "Luis Pedro Montejano",
    "Jorge Luis Ramírez Alfonsín"
  ],
  "comment": "10 pages, 2 figures, 1 table",
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $K\\_{[k,t]}$ be the complete graph on $k$ vertices from which a set of edges, induced by a clique of order $t$, has been dropped. In this note we give two explicit upper bounds for $R(K\\_{[k\\_1,t\\_1]},\\dots, K\\_{[k\\_r,t\\_r]})$ (the smallest integer $n$ such that for any $r$-edge coloring of $K\\_n$ there always occurs a monochromatic $K\\_{[k\\_i,t\\_i]}$ for some $i$). Our first upper bound contains a classical one in the case when $k\\_1=\\cdots =k\\_r$ and $t\\_i=1$ for all $i$. The second one is obtained by introducing a new edge coloring called {\\em $\\chi\\_r$-colorings}. We finally discuss a conjecture claiming, in particular, that our second upper bound improves the classical one in infinitely many cases.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2014-07-24T12:52:31.000Z",
      "abstract": "Let $K_{[k,t]}$ be the complete graph on $k$ vertices from which a set of edges, induced by a clique of order $t$, has been dropped. In this note we give two explicit upper bounds for $R(K_{[k_1,t_1]},\\dots, K_{[k_r,t_r]})$ (the smallest integer $n$ such that for any $r$-edge coloring of $K_n$ there always occurs a monochromatic $K_{[k_i,t_i]}$ for some $i$). Our first upper bound contains a classical one in the case when $k_1=\\cdots =k_r$ and $t_i=1$ for all $i$. The second one is obtained by introducing a new edge coloring called {\\em $\\chi_r$-colorings}. We finally discuss a conjecture claiming, in particular, that our second upper bound improves the classical one in infinitely many cases.",
      "comment": "9 pages, 2 figures, 1 table",
      "journal": null,
      "doi": null
    },
    {
      "version": "v3",
      "updated": "2014-12-12T13:03:44.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "complete graph",
      "dropped cliques",
      "first upper bound contains",
      "second upper bound",
      "explicit upper bounds"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 10,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2013arXiv1307.6327C"
    }
  }
}