Hostname: page-component-78c5997874-g7gxr Total loading time: 0 Render date: 2024-11-17T00:17:59.328Z Has data issue: false hasContentIssue false
  • English
  • Français

Graph limits of random unlabelled k-trees

Part of: Combinatorics Combinatorial probability Graph theory

Published online by Cambridge University Press:  18 May 2020

Emma Yu Jin  and
Benedikt Stufler
Emma Yu Jin
Affiliation:
Fakultät für Mathematik, Universität Wien, Oskar-Morgenstern Platz 1, 1090Vienna, Austria
Benedikt Stufler
Affiliation:
Institut für Mathematik, Universität München, Theresienstr. 39, D-80333Munich, Germany
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.

We study random unlabelled k-trees by combining the colouring approach by Gainer-Dewar and Gessel (2014) with the cycle-pointing method by Bodirsky, Fusy, Kang and Vigerske (2011). Our main applications are Gromov–Hausdorff–Prokhorov and Benjamini–Schramm limits that describe their asymptotic geometric shape on a global and local scale as the number of (k + 1)-cliques tends to infinity.

MSC classification

Primary: 60C05: Combinatorial probability
Secondary: 05C80: Random graphs 05A16: Asymptotic enumeration
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 29 , Issue 5 , September 2020 , pp. 722 - 746
Check for updates
Creative Commons
Creative Common License - CCCreative Common License - BY
This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted re-use, distribution, and reproduction in any medium, provided the original work is properly cited.
Copyright
© The Author(s), 2020. Published by Cambridge University Press

Footnotes

†

The first author was supported by FWF-MOST (Austrian–Taiwanese) project I 2309-N35 and FWF Project P 32305.

‡

The second author gratefully acknowledges support by the German Research Foundation DFG, STU 679/1-1 and the Swiss National Science Foundation grant number 200020_172515.

References

Aldous, D. (1991) The continuum random tree, II: An overview. In Stochastic Analysis (Durham, 1990), Vol. 167 of London Mathematical Society Lecture Note Series, Cambridge University Press, pp. 23–70.CrossRefGoogle Scholar
Beineke, L. W. and Pippert, R. E. (1969) The number of labeled k-dimensional trees. J. Combin. Theory 6 200–205.CrossRefGoogle Scholar
Bell, J. P., Burris, S. N. and Yeats, K. A. (2006) Counting rooted trees: The universal law t(n) ∼ Cρ −nn −3/2. Electron. J. Combin. 13 R63.CrossRefGoogle Scholar
Bergeron, F., Labelle, G. and Leroux, P. (1998) Combinatorial Species and Tree-Like Structures, Vol. 67 of Encyclopedia of Mathematics and its Applications, Cambridge University Press.Google Scholar
Bodirsky, M., Fusy, É., Kang, M. and Vigerske, S. (2011) Boltzmann samplers, Pólya theory, and cycle pointing. SIAM J. Comput. 40 721–769.CrossRefGoogle Scholar
Darrasse, A. and Soria, M. (2009) Limiting distribution for distances in k-trees. In Combinatorial Algorithms (IWOCA 2009) (Fiala, J.et al., eds), Vol. 5874 of Lecture Notes in Computer Science, Springer, pp. 170–182.CrossRefGoogle Scholar
Drmota, M. and Jin, E. Y. (2014) An asymptotic analysis of labeled and unlabeled k-trees. Algorithmica 75 579–605.CrossRefGoogle Scholar
Drmota, M., Jin, E. Y. and Stufler, B. (2019) Graph limits of random graphs from a subset of connected k-trees. Random Struct. Alg. 55 125–558.CrossRefGoogle ScholarPubMed
Durrett, R. T. and Iglehart, D. L. (1977) Functionals of Brownian meander and Brownian excursion. Ann. Probab. 5 130–135.CrossRefGoogle Scholar
Flajolet, P. and Sedgewick, R. (2010) Analytic Combinatorics, Cambridge University Press.Google Scholar
Foata, D. (1971) Enumerating k -trees. Discrete Math. 1 181–186.CrossRefGoogle Scholar
Fowler, T., Gessel, I., Labelle, G. and Leroux, P. (2002) The specification of 2-trees. Adv. Appl. Math. 28 145–168.CrossRefGoogle Scholar
Gainer-Dewar, A. (2012) Γ-species and the enumeration of k -trees. Electron. J. Combin. 19 P45.CrossRefGoogle Scholar
Gainer-Dewar, A. and Gessel, I. M. (2014) Counting unlabeled k -trees. J. Combin. Theory Ser. A 126 177–193.CrossRefGoogle Scholar
Harary, F. and Palmer, E. M. (1968) On acyclic simplicial complexes. Mathematika 15 115–122.CrossRefGoogle Scholar
Harary, F. and Palmer, E. M. (1973) Graphical Enumeration, Academic Press.Google Scholar
Iriza, A. D. (2015) Enumeration and random generation of unlabeled classes of graphs: A practical study of cycle-pointing and the dissymmetry theorem. Master’s thesis, Princeton University.Google Scholar
Joyal, A. (1981) Une théorie combinatoire des séries formelles. Adv. Math. 42 1–82.CrossRefGoogle Scholar
Miermont, G. (2009) Tessellations of random maps of arbitrary genus. Ann. Sci. Éc. Norm. Supér. 42 725–781.CrossRefGoogle Scholar
Moon, J. W. (1969) The number of labeled k -trees. J. Combin. Theory Ser. A 6 196–199.CrossRefGoogle Scholar
Otter, R. (1948) The number of trees. Ann. of Math. (2) 49 583–599.CrossRefGoogle Scholar
Pólya, G. (1937) Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen. Acta Math. 68 145–254.CrossRefGoogle Scholar
Stufler, B. (2016) Limits of random tree-like discrete structures. arXiv:1612.02580Google Scholar
Stufler, B. (2017) Asymptotic properties of random unlabelled block-weighted graphs. arXiv:1712.01301Google Scholar
Stufler, B. (2017) Scaling limits of random outerplanar maps with independent link-weights. Ann. Inst. H. Poincaré Probab. Statist. 53 900–915.CrossRefGoogle Scholar
Stufler, B. (2018) Gibbs partitions: The convergent case. Random Struct. Alg. 53 537–558.CrossRefGoogle Scholar
Stufler, B. (2018) Random enriched trees with applications to random graphs. Electron. J. Combin. 25 P3.11.CrossRefGoogle Scholar
Stufler, B. (2019) The continuum random tree is the scaling limit of unlabelled unrooted trees. Random Struct. Alg. 55 496–528.CrossRefGoogle Scholar
Stufler, B. (2020) Unlabelled Gibbs partitions. Combin. Probab. Comput. 29 293–309.CrossRefGoogle Scholar