FINITE SIZE SCALING FOR THE CORE OF LARGE RANDOM HYPERGRAPHS

• 成果类型: Article
• 署名作者: Dembo, Amir; Montanar, Andrea
• 署名单位: Stanford University; Stanford University; Stanford University
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/07-AAP514
• 发表日期: 2008
• 页码: 1993-2040
• 关键词: Random graphs; spin models; approximation; emergence; set

摘要

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 = np vertices and it hyperedges, each consisting of the same fixed number l >= 3 of vertices, the size of the core exhibits for large n a first-order phase transition, changing from o(n) for rho > rho(c) to a positive fraction of n for rho < rho(c), with a transition window size Theta(n(-1/2)) around rho(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(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.