Hostname: page-component-745bb68f8f-hvd4g Total loading time: 0 Render date: 2025-02-11T18:46:26.980Z Has data issue: false hasContentIssue false
  • English
  • Français

Counting Connected Hypergraphs via the Probabilistic Method

Published online by Cambridge University Press:  04 January 2016

BÉLA BOLLOBÁS  and
OLIVER RIORDAN
BÉLA BOLLOBÁS
Affiliation:
Department of Pure Mathematics and Mathematical Statistics, Wilberforce Road, Cambridge CB3 0WB, UK and Department of Mathematical Sciences, University of Memphis, Memphis TN 38152, USA (e-mail: b.bollobas@dpmms.cam.ac.uk)
OLIVER RIORDAN
Affiliation:
Mathematical Institute, University of Oxford, Radcliffe Observatory Quarter, Woodstock Road, Oxford OX2 6GG, UK (e-mail: riordan@maths.ox.ac.uk)
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.

In 1990 Bender, Canfield and McKay gave an asymptotic formula for the number of connected graphs on [n] = {1,2,. . .,n} with m edges, whenever n and the nullity m−n+1 tend to infinity. Let Cr(n,t) be the number of connected r-uniform hypergraphs on [n] with nullity t = (r−1)m−n+1, where m is the number of edges. For r ≥ 3, asymptotic formulae for Cr(n,t) are known only for partial ranges of the parameters: in 1997 Karoński and Łuczak gave one for t = o(log n/log log n), and recently Behrisch, Coja-Oghlan and Kang gave one for t=Θ(n). Here we prove such a formula for any fixed r ≥ 3 and any t = t(n) satisfying t = o(n) and t→∞ as n→∞, complementing the last result. This leaves open only the case t/n→∞, which we expect to be much simpler, and will consider in future work. The proof is based on probabilistic methods, and in particular on a bivariate local limit theorem for the number of vertices and edges in the largest component of a certain random hypergraph. We deduce this from the corresponding central limit theorem by smoothing techniques.

Keywords

Primary 05C80Secondary 05C6505C30
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 25 , Issue 1: Oberwolfach Special Issue Part 2 , January 2016 , pp. 21 - 75
Copyright
Copyright © Cambridge University Press 2015 

References

[1]Andriamampianina, T. and Ravelomanana, V. (2005) Enumeration of connected uniform hypergraphs. In Proc. 17th International Conference on Formal Power Series and Algebraic Combinatorics, Taormina: FPSAC 2005, pp. 387–398.Google Scholar
[2]Behrisch, M., Coja-Oghlan, A. and Kang, M. (2007) Local limit theorems and number of connected hypergraphs. arXiv:0706.0497Google Scholar
[3]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
[4]Behrisch, M., Coja-Oghlan, A. and Kang, M. (2010) The order of the giant component of random hypergraphs. Random Struct. Alg. 36 149–184.CrossRefGoogle Scholar
[5]Behrisch, M., Coja-Oghlan, A. and Kang, M. (2014) Local limit theorems for the giant component of random hypergraphs. Combin. Probab. Comput. 23 331–366.CrossRefGoogle Scholar
[6]Behrisch, M., Coja-Oghlan, A. and Kang, M. (2014) The asymptotic number of connected d-uniform hypergraphs. Combin. Probab. Comput. 23 367–385. Corrigendum: Combin. Probab. Comput. 24 (2015) 373–375.CrossRefGoogle Scholar
[7]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.CrossRefGoogle Scholar
[8]Bollobás, B. (1984) The evolution of sparse graphs. In Graph Theory and Combinatorics: Cambridge 1983, Academic Press, pp. 35–57.Google Scholar
[9]Bollobás, B. and Riordan, O. (2012) Asymptotic normality of the size of the giant component in a random hypergraph. Random Struct. Alg. 41 441–450.CrossRefGoogle Scholar
[10]Bollobás, B. and Riordan, O. Exploring hypergraphs with martingales. Random Struct. Alg., to appear. arXiv:1403.6558Google Scholar
[11]Bollobás, B. and Riordan, O. Counting connected hypergraphs via the probabilistic method, with appendix. arXiv:1404.5887Google Scholar
[12]Bollobás, B. and Riordan, O. Counting dense connected hypergraphs via the probabilistic method. arXiv:1511.04739Google Scholar
[13]Cayley, A. (1889) A theorem on trees. Quart. J. Pure and Applied Math. 23 376–378.Google Scholar
[14]Coja-Oghlan, A., Moore, C. and Sanwalani, V. (2007) Counting connected graphs and hypergraphs via the probabilistic method. Random Struct. Alg. 31 288–329.CrossRefGoogle Scholar
[15]Davis, B. and McDonald, D. (1995) An elementary proof of the local central limit theorem. J. Theoret. Probab. 8 693–701.CrossRefGoogle Scholar
[16]Erdős, P. and Rényi, A. (1960) On the evolution of random graphs. Magyar Tud. Akad. Mat. Kutató Int. Közl. 5 17–61.Google Scholar
[17]Karoński, M. and Łuczak, T. (1997) The number of connected sparsely edged uniform hypergraphs. Discrete Math. 171 153–167.CrossRefGoogle Scholar
[18]Karoński, M. and Łuczak, T. (2002) The phase transition in a random hypergraph. J. Comput. Appl. Math. 142 125–135.CrossRefGoogle Scholar
[19]Luczak, M. and Łuczak, T. (2006) The phase transition in the cluster-scaled model of a random graph. Random Struct. Alg. 28 215–246.CrossRefGoogle Scholar
[20]McDonald, D. R. (1979) On local limit theorem for integer valued random variables. Teor. Veroyatnost. i Primenen. 24 607–614. See also Theory Probab. Appl. 24 (1980) 613–619.Google Scholar
[21]Pittel, B. and Wormald, C. (2005) Counting connected graphs inside-out. J. Combin. Theory Ser. B 93 127–172.CrossRefGoogle Scholar
[22]Rényi, A. (1959) On connected graphs I (Hungarian, Russian summary). Magyar Tud. Akad. Mat. Kutató Int. Közl. 4 385–388.Google Scholar
[23]Sato, C. M. (2013) Core structures in random graphs and hypergraphs. PhD thesis, Department of Combinatorics and Optimization, University of Waterloo. https://uwspace.uwaterloo.ca/handle/10012/7787Google Scholar
[24]Sato, C. M. and Wormald, N. Asymptotic enumeration of sparse connected 3-uniform hypergraphs. arXiv:1401.7381Google Scholar
[25]Schmidt-Pruzan, J. and Shamir, E. (1985) Component structure in the evolution of random hypergraphs. Combinatorica 5 81–94.CrossRefGoogle Scholar
[26]Scott, A. and Tateno, A. On the number of triangles in a random graph. Manuscript.Google Scholar
[27]Selivanov, B. I. (1972) Enumeration of homogeneous hypergraphs with a simple cycle structure. Kombinatornyĭ Anal. 2 60–67.Google Scholar
[28]Wright, E. M. (1977) The number of connected sparsely edged graphs. J. Graph Theory 1 317–330.CrossRefGoogle Scholar
[29]Wright, E. M. (1978) The number of connected sparsely edged graphs II: Smooth graphs and blocks. J. Graph Theory 2 299–305.CrossRefGoogle Scholar
[30]Wright, E. M. (1980) The number of connected sparsely edged graphs III: Asymptotic results. J. Graph Theory 4 393–407.CrossRefGoogle Scholar
[31]Wright, E. M. (1983) The number of connected sparsely edged graphs {IV}: Large nonseparable graphs. J. Graph Theory 7 219–229.CrossRefGoogle Scholar