• search hit 2 of 28
Back to Result List

Local Limit Theorems and the Number of Connected Hypergraphs

Please always quote using this URN:urn:nbn:de:0296-matheon-3711
  • Let H_d(n, p) signify a random d-uniform hypergraph with n vertices in which each of the 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 derive local limit theorems for the joint distribution of the number of vertices and the number of edges in the largest component of H_d(n, p) and H_d(n,m). As an application, we obtain an asymptotic formula for the probability that H_d(n, p) is connected, and a corresponding formula for H_d(n,m). In addition, we infer a local limit theorem for the conditional distribution of the number of edges in H_d(n, p) given that H_d(n, p) is connected. While most prior work on this subject relies on techniques from enumerative combinatorics, we present a new, purely probabilistic approach.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Michael Behrisch, Amin Coja-Oghlan, Mihuyn Kang
URN:urn:nbn:de:0296-matheon-3711
Referee:Hans Jürgen Prömel
Document Type:Preprint, Research Center Matheon
Language:English
Date of first Publication:2007/07/01
Release Date:2007/05/01
Tag:
Institute:Humboldt-Universität zu Berlin
Preprint Number:365
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.