Counting graphic sequences via integrated random walks

Balister, Paul; Donderwinkel, Serte; Groenland, Carla; Johnston, Tom; Scott, Alex

doi:10.1090/tran/9403

Counting graphic sequences via integrated random walks
HTML articles powered by AMS MathViewer

by Paul Balister, Serte Donderwinkel, Carla Groenland, Tom Johnston and Alex Scott;

Trans. Amer. Math. Soc.

DOI: https://doi.org/10.1090/tran/9403

Published electronically: April 3, 2025

PDF | Request permission

Abstract:

Given an integer $n$, let $G(n)$ be the number of integer sequences $n-1\ge d_1\ge d_2\ge \dotsb \ge d_n\ge 0$ that are the degree sequence of some graph. We show that $G(n)=(c+o(1))4^n/n^{3/4}$ for some constant $c>0$, improving both the previously best upper and lower bounds by a factor of $n^{1/4}$ (up to polylog-factors).

Additionally, we answer a question of Royle, extend the values of $n$ for which $G(n)$ is known exactly from $n \leq 290$ to $n \leq 1651$ and determine the asymptotic probability that the integral of a (lazy) simple symmetric random walk bridge remains non-negative.

References

Céline Abraham, Jérémie Bettinelli, Gwendal Collet, and Igor Kortchemski, Random maps, Modélisation Aléatoire et Statistique—Journées MAS 2014, ESAIM Proc. Surveys, vol. 51, EDP Sci., Les Ulis, 2015, pp. 133–149. MR 3440795, DOI 10.1051/proc/201551008
David J. Aldous and Jim Pitman, Brownian bridge asymptotics for random mappings, Random Structures Algorithms 5 (1994), no. 4, 487–512. MR 1293075, DOI 10.1002/rsa.3240050402
Frank Aurzada and Thomas Simon, Persistence probabilities and exponents, Lévy matters. V, Lecture Notes in Math., vol. 2149, Springer, Cham, 2015, pp. 183–224. MR 3468226, DOI 10.1007/978-3-319-23138-9_{3}
Frank Aurzada, Steffen Dereich, and Mikhail Lifshits, Persistence probabilities for a bridge of an integrated simple random walk, Probab. Math. Statist. 34 (2014), no. 1, 1–22. MR 3225998
Alexander Barvinok and J. A. Hartigan, The number of graphs and a random graph with a given degree sequence, Random Structures Algorithms 42 (2013), no. 3, 301–348. MR 3039682, DOI 10.1002/rsa.20409
Michal Bassan, Serte Donderwinkel, and Brett Kolesnik. Graphical sequences and plane trees. preprint arXiv:2406.05110, 2024.
Frédérique Bassino, Mathilde Bouvel, Valentin Féray, Lucas Gerin, and Adeline Pierrot, The Brownian limit of separable permutations, Ann. Probab. 46 (2018), no. 4, 2134–2189. MR 3813988, DOI 10.1214/17-AOP1223
Jason Matthew Burns, The number of degree sequences of graphs, ProQuest LLC, Ann Arbor, MI, 2007. Thesis (Ph.D.)–Massachusetts Institute of Technology. MR 2717411
Amir Dembo, Jian Ding, and Fuchang Gao, Persistence of iterated partial sums, Ann. Inst. Henri Poincaré Probab. Stat. 49 (2013), no. 3, 873–884 (English, with English and French summaries). MR 3112437, DOI 10.1214/11-AIHP452
Denis Denisov and Vitali Wachtel, Exit times for integrated random walks, Ann. Inst. Henri Poincaré Probab. Stat. 51 (2015), no. 1, 167–193. MR 3300967, DOI 10.1214/13-AIHP577
Serte Donderwinkel and Brett Kolesnik. Asymptotics for Sinaĭ excursions, Preprint, arXiv:2403.12941, 2024.
Paul Erdős and Tibor Gallai. Graphs with prescribed degrees of vertices [Hungarian]. Mat. Lapok., 11:\penalty0 264–274, 1960.
P. Erdős and L. B. Richmond, On graphical partitions, Combinatorica 13 (1993), no. 1, 57–63. MR 1221176, DOI 10.1007/BF01202789
William Feller, An introduction to probability theory and its applications. Vol. II, 2nd ed., John Wiley & Sons, Inc., New York-London-Sydney, 1971. MR 270403
Jean-François Le Gall, Random trees and applications, Probab. Surv. 2 (2005), 245–311. MR 2203728, DOI 10.1214/154957805100000140
Fuchang Gao, Zhenxia Liu, and Xiangfeng Yang, Conditional persistence of Gaussian random walks, Electron. Commun. Probab. 19 (2014), no. 70, 9. MR 3269170, DOI 10.1214/ECP.v19-3587
S. L. Hakimi, On realizability of a set of integers as degrees of the vertices of a linear graph. I, J. Soc. Indust. Appl. Math. 10 (1962), 496–506. MR 148049
Werner Hässelbarth, Die Verzweigtheit von Graphen, Match 16 (1984), 3–17 (German). MR 781036
Václav Havel, Eine Bemerkung über die Existenz der endlichen Graphen, Časopis Pěst. Mat. 80 (1955), 477–480 (Czech, with German and Russian summaries). MR 89165
Antal Iványi and Loránd Lucz. Erdős–Gallai test in linear time, Combinatorica, 4, 2011.
Antal Iványi, Loránd Lucz, Tamás Matuszka, and Shariefuddin Pirzada. Parallel enumeration of degree sequences of simple graphs, Acta Univ. Sapientiae Inform., 4 no. 2, 260–288, 2012.
Antal Iványi, Gergő Gombos, Loránd Lucz, and Tamás Matuszka. Parallel enumeration of degree sequences of simple graphs II, Acta Univ. Sapientiae Inform., 5, no. 2, 245–270, 2013.
Jeong Han Kim and Boris Pittel, Confirming the Kleitman-Winston conjecture on the largest coefficient in a $q$-Catalan number, J. Combin. Theory Ser. A 92 (2000), no. 2, 197–206. MR 1796474, DOI 10.1006/jcta.1999.3054
D. Kleitman, The number of tournament score sequences for a large number of players, Combinatorial Structures and their Applications (Proc. Calgary Internat. Conf., Calgary, Alta., 1969) Gordon and Breach, New York-London-Paris, 1970, pp. 209–213. MR 270932
Brett Kolesnik, The asymptotic number of score sequences, Combinatorica 43 (2023), no. 4, 827–844. MR 4632171, DOI 10.1007/s00493-023-00037-4
Xuesong Lu and Stéphane Bressan. 2011 Generating random graphic sequences, Database Systems for Advanced Applications, pages 570–579. Springer, Berlin, Heidelberg.
Percy Alexander MacMahon. An American tournament treated by the calculus of symmetric functions. Quarterly Journal of Pure and Applied Mathematics, 49:\penalty0 1–36, 1920.
Brendan D. McKay, Asymptotics for symmetric $0$-$1$ matrices with prescribed row sums, Ars Combin. 19 (1985), no. A, 15–25. MR 790916
Brendan D. McKay and Nicholas C. Wormald, Asymptotic enumeration by degree sequence of graphs of high degree, European J. Combin. 11 (1990), no. 6, 565–580. MR 1078713, DOI 10.1016/S0195-6698(13)80042-X
Brendan D. McKay and Nicholas C. Wormald, Asymptotic enumeration by degree sequence of graphs with degrees $o(n^{1/2})$, Combinatorica 11 (1991), no. 4, 369–382. MR 1137769, DOI 10.1007/BF01275671
Stephen Melczer, Marcus Michelen, and Somabha Mukherjee, Asymptotic bounds on graphical partitions and partition comparability, Int. Math. Res. Not. IMRN 4 (2021), 2842–2860. MR 4218339, DOI 10.1093/imrn/rnaa251
John W. Moon, Topics on tournaments, Holt, Rinehart and Winston, New York-Montreal, Que.-London, 1968. MR 256919
Leo Moser, Asymptotics of tournament scores, Combinatorics (Proc. Sympos. Pure Math., Vol. XIX, Univ. California, Los Angeles, Calif., 1968) Proc. Sympos. Pure Math., Vol. XIX, Amer. Math. Soc., Providence, RI, 1971, pp. 165–166. MR 314685
Crispin St. John Alvah Nash-Williams. Valency sequences which force graphs to have Hamiltonian circuits, University of Waterloo Research Report, Waterloo, Ontario, 1969.
Boris Pittel, Confirming two conjectures about the integer partitions, J. Combin. Theory Ser. A 88 (1999), no. 1, 123–135. MR 1713480, DOI 10.1006/jcta.1999.2986
C. C. Rousseau and Firasath Ali, A note on graphical partitions, J. Combin. Theory Ser. B 64 (1995), no. 2, 314–318. MR 1339855, DOI 10.1006/jctb.1995.1038
Gordon Royle. The on-line encyclopedia of integer sequences, 2006.
Frank Ruskey, Robert Cohen, Peter Eades, and Aaron Scott, Alley CATs in search of good homes, Proceedings of the Twenty-fifth Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 1994), 1994, pp. 97–110. MR 1382363
Gerard Sierksma and Han Hoogeveen, Seven criteria for integer sequences being graphic, J. Graph Theory 15 (1991), no. 2, 223–231. MR 1106533, DOI 10.1002/jgt.3190150209
Ya. G. Sinaĭ, Distribution of some functionals of the integral of a random walk, Teoret. Mat. Fiz. 90 (1992), no. 3, 323–353 (Russian, with English and Russian summaries); English transl., Theoret. and Math. Phys. 90 (1992), no. 3, 219–241. MR 1182301, DOI 10.1007/BF01036528
Richard P. Stanley, A zonotope associated with graphical degree sequences, Applied geometry and discrete mathematics, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 4, Amer. Math. Soc., Providence, RI, 1991, pp. 555–570. MR 1116376, DOI 10.1090/dimacs/004/42
Vladislav Vysotsky, On the probability that integrated random walks stay positive, Stochastic Process. Appl. 120 (2010), no. 7, 1178–1193. MR 2639743, DOI 10.1016/j.spa.2010.03.005
Vladislav Vysotsky, Positivity of integrated random walks, Ann. Inst. Henri Poincaré Probab. Stat. 50 (2014), no. 1, 195–213 (English, with English and French summaries). MR 3161528, DOI 10.1214/12-AIHP487
Kai Wang, Efficient counting of degree sequences, Discrete Math. 342 (2019), no. 3, 888–897. MR 3891763, DOI 10.1016/j.disc.2018.11.024
Kai Wang. An improved algorithm for counting graphical degree sequences of given length. 2019 International Conference on Computational Science and Computational Intelligence (CSCI), pages 451–456, 2019b.
Kenneth J. Winston and Daniel J. Kleitman, On the asymptotic number of tournament score sequences, J. Combin. Theory Ser. A 35 (1983), no. 2, 208–230. MR 712106, DOI 10.1016/0097-3165(83)90008-0
Nicholas Wormald, Asymptotic enumeration of graphs with given degree sequence, Proceedings of the International Congress of Mathematicians—Rio de Janeiro 2018. Vol. IV. Invited lectures, World Sci. Publ., Hackensack, NJ, 2018, pp. 3245–3264. MR 3966531

AMS Website Down

Transactions of the American Mathematical Society

Counting graphic sequences via integrated random walks
HTML articles powered by AMS MathViewer

Abstract: