Local Limit Theorems for the Giant Component of Random Hypergraphs†. (May 2014)

• Record Type: Journal Article
• Authors: BEHRISCH, MICHAEL; COJA-OGHLAN, AMIN; KANG, MIHYUN
• Is Part Of: Combinatorics, probability and computing. Volume 23:Number 3(2014:May)
• Page Start: 331
• Page End: 366
• Publication Date: 2014-05
• Subjects: Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548314000017
• Languages: English
• ISSNs: 0963-5483

Abstract

<abstract abstract-type="normal"> <title> <x content-type="archive" xml:space="preserve">Abstract</x> </title> <p>Let <italic>H_d(n, p)</italic> signify a random <italic>d</italic>-uniform hypergraph with <italic>n</italic> vertices in which each of the <inline-formula><alternatives><inline-graphic xlink:href="ark:/27927/pgg5h7wzgsd" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><tex-math><![CDATA[$\binom{n}{d}$]]></tex-math></alternatives></inline-formula> possible edges is present with probability <italic>p</italic>=<italic>p(n)</italic> independently, and let <italic>H_d(n, m)</italic> denote a uniformly distributed <italic>d</italic>-uniform hypergraph with <italic>n</italic> vertices and <italic>m</italic> edges. We derive local limit theorems for the joint distribution of the number of vertices and the number of edges in the largest component of <italic>H_d(n, p)</italic> and <italic>H_d(n, m)</italic> in the regime <inline-formula><alternatives><inline-graphic xlink:href="ark:/27927/pgg5h7wzgw2" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><tex-math><![CDATA[$(d-1)\binom{n-1}{d-1}p>1+\varepsilon$]]></tex-math></alternatives></inline-formula>, resp. <italic>d(d−1)m/n</italic>&gt;1+ϵ, where ϵ&gt;0 is arbitrarily small but fixed as <italic>n</italic> → ∞. The proofs are based on a purely probabilistic approach.</p> </abstract>