{
  "id": "1801.06466",
  "version": "v1",
  "published": "2018-01-19T15:39:59.000Z",
  "updated": "2018-01-19T15:39:59.000Z",
  "title": "Spectral expansion of random sum complexes",
  "authors": [
    "Orr Beit-Aharon",
    "Roy Meshulam"
  ],
  "comment": "12 pages, one figure",
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $G$ be a finite abelian group of order $n$ and let $\\Delta_{n-1}$ denote the $(n-1)$-simplex on the vertex set $G$. The sum complex $X_{A,k}$ associated to a subset $A \\subset G$ and $k < n$, is the $k$-dimensional simplicial complex obtained by taking the full $(k-1)$-skeleton of $\\Delta_{n-1}$ together with all $(k+1)$-subsets $\\sigma \\subset G$ that satisfy $\\sum_{x \\in \\sigma} x \\in A$. Let $C^{k-1}(X_{A,k})$ denote the space of complex valued $(k-1)$-cochains of $X_{A,k}$. Let $L_{k-1}:C^{k-1}(X_{A,k}) \\rightarrow C^{k-1}(X_{A,k})$ denote the reduced $(k-1)$-th Laplacian of $X_{A,k}$, and let $\\mu_{k-1}(X_{A,k})$ be the minimal eigenvalue of $L_{k-1}$. It is shown that for any $k \\geq 1$ and $\\epsilon>0$ there exists a constant $c(k,\\epsilon)$ such that if $A$ is a random subset of $G$ of size $m=\\lceil c(k,\\epsilon) \\log n \\rceil$, then $\\mu_{k-1}(X_{A,k}) > (1-\\epsilon)m$ asymptotically almost surely.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-01-19T15:39:59.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05E45",
      "60C05"
    ],
    "keywords": [
      "random sum complexes",
      "spectral expansion",
      "dimensional simplicial complex",
      "finite abelian group",
      "random subset"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 12,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}