{
  "id": "1911.09377",
  "version": "v1",
  "published": "2019-11-21T10:06:22.000Z",
  "updated": "2019-11-21T10:06:22.000Z",
  "title": "The asymptotics of the clustering transition for random constraint satisfaction problems",
  "authors": [
    "Louise Budzynski",
    "Guilhem Semerjian"
  ],
  "comment": "35 pages, 8 figures; Submission to SciPost",
  "categories": [
    "cond-mat.dis-nn",
    "cs.DM",
    "math.PR"
  ],
  "abstract": "Random Constraint Satisfaction Problems exhibit several phase transitions when their density of constraints is varied. One of these threshold phenomena, known as the clustering or dynamic transition, corresponds to a transition for an information theoretic problem called tree reconstruction. In this article we study this threshold for two CSPs, namely the bicoloring of $k$-uniform hypergraphs with a density $\\alpha$ of constraints, and the $q$-coloring of random graphs with average degree $c$. We show that in the large $k,q$ limit the clustering transition occurs for $\\alpha = \\frac{2^{k-1}}{k} (\\ln k + \\ln \\ln k + \\gamma_{\\rm d} + o(1))$, $c= q (\\ln q + \\ln \\ln q + \\gamma_{\\rm d}+ o(1))$, where $\\gamma_{\\rm d}$ is the same constant for both models. We characterize $\\gamma_{\\rm d}$ via a functional equation, solve the latter numerically to estimate $\\gamma_{\\rm d} \\approx 0.871$, and obtain an analytic lowerbound $\\gamma_{\\rm d} \\ge 1 + \\ln (2 (\\sqrt{2}-1)) \\approx 0.812$. Our analysis unveils a subtle interplay of the clustering transition with the rigidity (naive reconstruction) threshold that occurs on the same asymptotic scale at $\\gamma_{\\rm r}=1$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-11-21T10:06:22.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "random constraint satisfaction problems",
      "clustering transition",
      "asymptotic",
      "information theoretic problem",
      "average degree"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 35,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}