{
  "id": "2010.12329",
  "version": "v1",
  "published": "2020-10-22T11:48:15.000Z",
  "updated": "2020-10-22T11:48:15.000Z",
  "title": "Erdös-Hajnal Conjecture for New Infinite Families of Tournaments",
  "authors": [
    "Soukaina Zayat",
    "Salman Ghazal"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "Erd\\\"{o}s-Hajnal conjecture states that for every undirected graph $H$ there exists $ \\epsilon(H) > 0 $ such that every undirected graph on $ n $ vertices that does not contain $H$ as an induced subgraph contains a clique or a stable set of size at least $ n^{\\epsilon(H)} $. This conjecture has a directed equivalent version stating that for every tournament $H$ there exists $ \\epsilon(H) > 0 $ such that every $H-$free $n-$vertex tournament $T$ contains a transitive subtournament of order at least $ n^{\\epsilon(H)} $. This conjecture is known to hold for a few infinite families of tournaments. In this paper we construct two new infinite families of tournaments - the family of so-called galaxies with spiders and the family of so-called asterisms, and we prove the correctness of the conjecture for these two families.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-10-22T11:48:15.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "infinite families",
      "erdös-hajnal conjecture",
      "undirected graph",
      "directed equivalent version",
      "conjecture states"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}