Hostname: page-component-cd9895bd7-gbm5v Total loading time: 0 Render date: 2024-12-29T02:16:11.305Z Has data issue: false hasContentIssue false
  • English
  • Français

Unlabelled Gibbs partitions

Part of: Probability theory on algebraic and topological structures Combinatorics Combinatorial probability

Published online by Cambridge University Press:  04 November 2019

Benedikt Stufler
Benedikt Stufler*
Affiliation:
Institut für Mathematik, Universität Zürich, Winterthurerstrasse 190, CH-8057, Zürich, Switzerland
*
Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We study random composite structures considered up to symmetry that are sampled according to weights on the inner and outer structures. This model may be viewed as an unlabelled version of Gibbs partitions and encompasses multisets of weighted combinatorial objects. We describe a general setting characterized by the formation of a giant component. The collection of small fragments is shown to converge in total variation toward a limit object following a Pólya–Boltzmann distribution.

MSC classification

Primary: 60C05: Combinatorial probability 05A18: Partitions of sets
Secondary: 60B10: Convergence of probability measures
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 29 , Issue 2 , March 2020 , pp. 293 - 309
Copyright
© Cambridge University Press 2019

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Arratia, R., Barbour, A. D. and Tavaré, S. (2003) Logarithmic Combinatorial Structures: A Probabilistic Approach, EMS Monographs in Mathematics, European Mathematical Society.CrossRefGoogle Scholar
Barbour, A. D. and Granovsky, B. L. (2005) Random combinatorial structures: The convergent case. J. Combin. Theory Ser. A 109 203–220.CrossRefGoogle Scholar
Bell, J. P., Bender, E. A., Cameron, P. J. and Richmond, L. B. (2000) Asymptotics for the probability of connectedness and the distribution of number of components. Electron. J. Combin. 7 R3.Google 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
Chover, J., Ney, P. and Wainger, S. (1973) Functions of probability measures. J. Analyse Math. 26 255–302.CrossRefGoogle Scholar
Duchon, P., Flajolet, P., Louchard, G. and Schaeffer, G. (2004) Boltzmann samplers for the random generation of combinatorial structures Combin. Probab. Comput. 13 577–625.CrossRefGoogle Scholar
Embrechts, P. (1983) The asymptotic behaviour of series and power series with positive coefficients. Med. Konink. Acad. Wetensch. België 45 41–61.Google Scholar
Embrechts, P. and Omey, E. (1984) Functions of power series. Yokohama Math. J. 32 77–88.Google Scholar
Erlihson, M. M. and Granovsky, B. L. (2008) Limit shapes of Gibbs distributions on the set of integer partitions: The expansive case. Ann. Inst. Henri Poincaré Probab. Statist. 44 915–945.CrossRefGoogle Scholar
Flajolet, P., Fusy, É. and Pivoteau, C. (2007) Boltzmann sampling of unlabelled structures. In Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments and the Fourth Workshop on Analytic Algorithmics and Combinatorics, SIAM, pp. 201–211.CrossRefGoogle Scholar
Flajolet, P. and Sedgewick, R. (2009) Analytic Combinatorics, Cambridge University Press.CrossRefGoogle Scholar
Foss, S., Korshunov, D. and Zachary, S. (2013) An Introduction to Heavy-Tailed and Subexponential Distributions, second edition, Springer Series in Operations Research and Financial Engineering, Springer.CrossRefGoogle Scholar
Joyal, A. (1981) Une théorie combinatoire des séries formelles. Adv. Math. 42 1–82.CrossRefGoogle Scholar
McDiarmid, C. (2008) Random graphs on surfaces. J. Combin. Theory Ser. B 98 778–797.CrossRefGoogle Scholar
McDiarmid, C. (2009) Random graphs from a minor-closed class. Combin. Probab. Comput. 18 583–599.CrossRefGoogle Scholar
Mutafchiev, L. (1998) The largest tree in certain models of random forests. Random Struct. Alg. 13 211–228.3.0.CO;2-Y>CrossRefGoogle Scholar
Pitman, J. (2006) Combinatorial Stochastic Processes, Vol. 1875 of Lecture Notes in Mathematics, Springer.Google Scholar
Stufler, B. (2017) Asymptotic properties of random unlabelled block-weighted graphs. arXiv:1712.01301Google Scholar
Stufler, B. (2018) Gibbs partitions: The convergent case. Random Struct. Alg. 53 537–558.CrossRefGoogle Scholar