{
  "id": "math/0702007",
  "version": "v2",
  "published": "2007-02-01T01:47:08.000Z",
  "updated": "2008-11-17T07:01:36.000Z",
  "title": "Finite size scaling for the core of large random hypergraphs",
  "authors": [
    "Amir Dembo",
    "Andrea Montanari"
  ],
  "comment": "Published in at http://dx.doi.org/10.1214/07-AAP514 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)",
  "journal": "Annals of Applied Probability 2008, Vol. 18, No. 5, 1993-2040",
  "doi": "10.1214/07-AAP514",
  "categories": [
    "math.PR",
    "math.CO"
  ],
  "abstract": "The (two) core of a hypergraph is the maximal collection of hyperedges within which no vertex appears only once. It is of importance in tasks such as efficiently solving a large linear system over GF[2], or iterative decoding of low-density parity-check codes used over the binary erasure channel. Similar structures emerge in a variety of NP-hard combinatorial optimization and decision problems, from vertex cover to satisfiability. For a uniformly chosen random hypergraph of $m=n\\rho$ vertices and $n$ hyperedges, each consisting of the same fixed number $l\\geq3$ of vertices, the size of the core exhibits for large $n$ a first-order phase transition, changing from $o(n)$ for $\\rho>\\rho _{\\mathrm{c}}$ to a positive fraction of $n$ for $\\rho<\\rho_{\\mathrm{c}}$, with a transition window size $\\Theta(n^{-1/2})$ around $\\rho_{\\mathrm{c}}>0$. Analyzing the corresponding ``leaf removal'' algorithm, we determine the associated finite-size scaling behavior. In particular, if $\\rho$ is inside the scaling window (more precisely, $\\rho=\\rho_{\\mathrm{c}}+rn^{-1/2}$), the probability of having a core of size $\\Theta(n)$ has a limit strictly between 0 and 1, and a leading correction of order $\\Theta(n^{-1/6})$. The correction admits a sharp characterization in terms of the distribution of a Brownian motion with quadratic shift, from which it inherits the scaling with $n$. This behavior is expected to be universal for a wide collection of combinatorial problems.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2008-11-17T07:01:36.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C80",
      "60J10",
      "60F17",
      "68R10",
      "94A29"
    ],
    "keywords": [
      "large random hypergraphs",
      "finite size scaling",
      "binary erasure channel",
      "first-order phase transition",
      "low-density parity-check codes"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2007math......2007D"
    }
  }
}