Hostname: page-component-74656f9884-c52kr Total loading time: 0 Render date: 2026-11-09T08:04:00.478Z Has data issue: false hasContentIssue false
  • English
  • Français

The Asymptotic Number of Connected d-Uniform Hypergraphs†

Published online by Cambridge University Press:  13 February 2014

MICHAEL BEHRISCH ,
AMIN COJA-OGHLAN  and
MIHYUN KANG
MICHAEL BEHRISCH
Affiliation:
Institute of Transportation Systems, German Aerospace Center, Rutherfordstrasse 2, 12489 Berlin, Germany (e-mail: michael.behrisch@dlr.de)
AMIN COJA-OGHLAN
Affiliation:
Goethe University, Mathematics Institute, 60054 Frankfurt am Main, Germany (e-mail: acoghlan@math.uni-frankfurt.de)
MIHYUN KANG
Affiliation:
TU Graz, Institut für Optimierung und Diskrete Mathematik (Math B), Steyrergasse 30, 8010 Graz, Austria (e-mail: kang@math.tugraz.at)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

For d ≥ 2, let Hd(n,p) denote a random d-uniform hypergraph with n vertices in which each of the $\binom{n}{d}$ possible edges is present with probability p=p(n) independently, and let Hd(n,m) denote a uniformly distributed d-uniform hypergraph with n vertices and m edges. Let either H=Hd(n,m) or H=Hd(n,p), where m/n and $\binom{n-1}{d-1}p$ need to be bounded away from (d−1)−1 and 0 respectively. We determine the asymptotic probability that H is connected. This yields the asymptotic number of connected d-uniform hypergraphs with given numbers of vertices and edges. We also derive a local limit theorem for the number of edges in Hd(n,p), conditioned on Hd(n,p) being connected.

Keywords

Primary 05C80Secondary 05C65

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 23 , Issue 3 , May 2014 , pp. 367 - 385
Copyright
Copyright © Cambridge University Press 2014 

Footnotes

†

An extended abstract version of this work appeared in the proceedings of RANDOM 2007, Vol. 4627 of Lecture Notes in Computer Science, Springer, pp. 341–352.

References

[1]Andriamampianina, T. and Ravelomanana, V. (2005) Enumeration of connected uniform hypergraphs. In Proc. FPSAC 2005.Google Scholar
[2]Behrisch, M., Coja-Oghlan, A. and Kang, M. (2007) Local limit theorems for the giant component of random hypergraphs. In Proc. RANDOM 2007, Vol. 4627 of Lecture Notes in Computer Science, Springer, pp. 341–352.Google Scholar
[3]Behrisch, M., Coja-Oghlan, A. and Kang, M. (2010) The order of the giant component of random hypergraphs. Random Struct. Alg. 36 149–184.Google Scholar
[4]Behrisch, M., Coja-Oghlan, A. and Kang, M. (2014) Local limit theorems for the giant component of random hypergraphs. Combin. Probab. Comput. doi:10.1017/S0963548314000017CrossRefGoogle Scholar
[5]Bender, E. A., Canfield, E. R. and McKay, B. D. (1990) The asymptotic number of labeled connected graphs with a given number of vertices and edges. Random Struct. Alg. 1 127–169.Google Scholar
[6]Bender, E. A., Canfield, E. R. and McKay, B. D. (1992) Asymptotic properties of labeled connected graphs. Random Struct. Alg. 3 183–202.Google Scholar
[7]Bollobás, B. (2001) Random Graphs, second edition, Cambridge University Press.CrossRefGoogle Scholar
[8]Coja-Oghlan, A., Moore, C. and Sanwalani, V. (2007) Counting connected graphs and hypergraphs via the probabilistic method. Random Struct. Alg. 31 288–329.Google Scholar
[9]Erdős, P. and Rényi, A. (1959) On random graphs I. Publicationes Math. Debrecen 5 290–297.Google Scholar
[10]Erdős, P. and Rényi, A. (1960) On the evolution of random graphs. Publ. Math. Inst. Hungar. Acad. Sci. 5 17–61.Google Scholar
[11]van der Hofstad, R. and Spencer, J. (2006) Counting connected graphs asymptotically. European J. Combin. 27 1294–1320.Google Scholar
[12]Janson, S., Łuczak, T. and Ruciński, A. (2000) Random Graphs, Wiley.Google Scholar
[13]Karoński, M. and Łuczak, T. (1997) The number of connected sparsely edged uniform hypergraphs. Discrete Math. 171 153–168.Google Scholar
[14]Łuczak, T. (1990) On the number of sparse connected graphs. Random Struct. Alg. 1 171–173.Google Scholar
[15]O'Connell, N. (1998) Some large deviation results for sparse random graphs. Probab. Theory Rel. Fields 110 277–285.Google Scholar
[16]Pittel, B. and Wormald, N. C. (2005) Counting connected graphs inside out. J. Combin. Theory Ser. B 93 127–172.Google Scholar
[17]Schmidt-Pruzan, J. and Shamir, E. (1985) Component structure in the evolution of random hypergraphs. Combinatorica 5 81–94.Google Scholar
[18]Stepanov, V. E. (1970) On the probability of connectedness of a random graph gm(t). Theory Probab. Appl. 15 55–67.Google Scholar