{
  "id": "1309.7375",
  "version": "v2",
  "published": "2013-09-27T21:54:31.000Z",
  "updated": "2015-06-03T16:26:34.000Z",
  "title": "Random subcube intersection graphs I: cliques and covering",
  "authors": [
    "Victor Falgas-Ravry",
    "Klas Markström"
  ],
  "comment": "38 pages, 1 figure",
  "categories": [
    "math.PR",
    "math.CO"
  ],
  "abstract": "We study random subcube intersection graphs, that is, graphs obtained by selecting a random collection of subcubes of a fixed hypercube $Q_d$ to serve as the vertices of the graph, and setting an edge between a pair of subcubes if their intersection is non-empty. Our motivation for considering such graphs is to model `random compatibility' between vertices in a large network. For both of the models considered in this paper, we determine the thresholds for covering the underlying hypercube $Q_d$ and for the appearance of s-cliques. In addition we pose some open problems.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2013-09-27T21:54:31.000Z",
      "abstract": "We study random subcube intersection graphs, that is, graphs obtained by selecting a random collection of subcubes of a fixed hypercube Q_d to serve as the vertices of the graph, and setting an edge between a pair of subcubes if their intersection is non-empty. Our motivation for considering such graphs is to model `random compatibility' between vertices in a large network. For both of the models considered in this paper, we determine the thresholds for covering the underlying hypercube Q_d and for the appearance of s-cliques. In addition we pose a number of open problems.",
      "comment": "36 pages, 1 figure. Part of this work was presented by the first author at the Random Structures & Algorithms conference in Pozna\\'n in August 2013",
      "journal": null,
      "doi": null
    },
    {
      "version": "v2",
      "updated": "2015-06-03T16:26:34.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60C05",
      "60K35",
      "05C80",
      "G.2.2",
      "G.3"
    ],
    "keywords": [
      "study random subcube intersection graphs",
      "random collection",
      "large network",
      "random compatibility",
      "open problems"
    ],
    "tags": [
      "conference paper"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 38,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2013arXiv1309.7375F"
    }
  }
}