Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

Local Limit Theorems for the Giant Component of Random Hypergraphs

Michael BehrischContact Information, Amin Coja-OghlanContact Information and Mihyun KangContact Information

(5)  Humboldt-Universität zu Berlin, Institut für Informatik, Unter den Linden 6, 10099 Berlin, Germany
(6)  Carnegie Mellon University, Department of Mathematical Sciences, Pittsburgh, PA 15213, USA
Abstract
Let H d (n,p) signify a random d-uniform hypergraph with n vertices in which each of the ${n}\choose{d}$ possible edges is present with probability p = p(n) independently, and let H d (n,m) denote a uniformly distributed d-uniform hypergraph with n vertices and m edges. We establish a local limit theorem for the number of vertices and edges in the largest component of H d (n,p) in the regime , thereby determining the joint distribution of these parameters precisely. As an application, we derive an asymptotic formula for the probability that H d (n,m) is connected, thus obtaining a formula for the asymptotic number of connected hypergraphs with a given number of vertices and edges. While most prior work on this subject relies on techniques from enumerative combinatorics, we present a new, purely probabilistic approach.

Contact Information Michael Behrisch
Email: behrisch@informatik.hu-berlin.de

Contact Information Amin Coja-Oghlan
Email: coja@informatik.hu-berlin.de

Contact Information Mihyun Kang
Email: kang@informatik.hu-berlin.de
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.112 • Server: mpweb06
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)