{
  "id": "1112.3015",
  "version": "v1",
  "published": "2011-12-13T20:14:34.000Z",
  "updated": "2011-12-13T20:14:34.000Z",
  "title": "Induced subgraphs of hypercubes",
  "authors": [
    "Geir Agnarsson"
  ],
  "comment": "16 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $Q_k$ denote the $k$-dimensional hypercube on $2^k$ vertices. A vertex in a subgraph of $Q_k$ is {\\em full} if its degree is $k$. We apply the Kruskal-Katona Theorem to compute the maximum number of full vertices an induced subgraph on $n\\leq 2^k$ vertices of $Q_k$ can have, as a function of $k$ and $n$. This is then used to determine $\\min(\\max(|V(H_1)|, |V(H_2)|))$ where (i) $H_1$ and $H_2$ are induced subgraphs of $Q_k$, and (ii) together they cover all the edges of $Q_k$, that is $E(H_1)\\cup E(H_2) = E(Q_k)$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2011-12-13T20:14:34.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05A15",
      "05C35"
    ],
    "keywords": [
      "induced subgraph",
      "dimensional hypercube",
      "full vertices",
      "kruskal-katona theorem",
      "maximum number"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 16,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2011arXiv1112.3015A"
    }
  }
}