{
  "id": "1803.05246",
  "version": "v1",
  "published": "2018-03-14T12:59:23.000Z",
  "updated": "2018-03-14T12:59:23.000Z",
  "title": "On the connectivity threshold for colorings of random graphs and hypergraphs",
  "authors": [
    "Michael Anastos",
    "Alan Frieze"
  ],
  "comment": "15 pages",
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "Let $\\Omega_q=\\Omega_q(H)$ denote the set of proper $[q]$-colorings of the hypergraph $H$. Let $\\Gamma_q$ be the graph with vertex set $\\Omega_q$ and an edge ${\\sigma,\\tau\\}$ where $\\sigma,\\tau$ are colorings iff $h(\\sigma,\\tau)=1$. Here $h(\\sigma,\\tau)$ is the Hamming distance $|\\{v\\in V(H):\\sigma(v)\\neq\\tau(v)\\}|$. We show that if $H=H_{n,m;k},\\,k\\geq 2$, the random $k$-uniform hypergraph with $V=[n]$ and $m=dn/k$ then w.h.p. $\\Gamma_q$ is connected if $d$ is sufficiently large and $q\\gtrsim (d/\\log d)^{1/(k-1)}$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-03-14T12:59:23.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "random graphs",
      "connectivity threshold",
      "vertex set",
      "uniform hypergraph"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 15,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}