Limits for embedding distributions. (English) Zbl 1462.05117
Summary: In this paper, we first establish a version of the central limit theorem for a double sequence \(\{ p_i(n) \}\) that satisfies a linear recurrence relation. Then we find and prove that under some commonly observed conditions, the sequence of embedding distributions of an \(H\)-linear family of graphs with spiders is asymptotic to a normal distribution. Applications are given to some well-known path-like and ring-like sequences of graphs. We also prove that the limit for the Euler-genus distributions of a sequence of graphs is the same as the limit for the crosscap-number distributions of that sequence.
MSC:
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
| 05A15 | Exact enumeration problems, generating functions |
| 05C30 | Enumeration in graph theory |
| 05D40 | Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) |
Keywords:
central limit theorem; embedding distributions; limits; \(H\)-linear family of graphs with spiders; normal distributionReferences:
| [1] | Behrends, E., Introduction to Markov Chains (2000), Vieweg+Teubner Verlag: Vieweg+Teubner Verlag Wesbaden · Zbl 0953.60063 |
| [2] | Chen, J.; Gross, J. L., Limit points for average genus. I: 3-connected and 2-connected simplicial graphs, J. Comb. Theory, Ser. B, 55, 82-103 (1992) · Zbl 0709.05017 |
| [3] | Chen, J.; Gross, J. L.; Rieper, R. G., Overlap matrices and total imbedding distributions, Discrete Math., 128, 1-3, 73-94 (1994) · Zbl 0798.05017 |
| [4] | Chen, Y.; Gross, J. L., An Euler-genus approach to the calculation of the crosscap-number polynomial, J. Graph Theory, 88, 1, 80-100 (2018) · Zbl 1393.05159 |
| [5] | Chen, Y.; Gross, J. L.; Mansour, T., On the genus distributions of wheels and of related graphs, Discrete Math., 341, 934-945 (2018) · Zbl 1380.05004 |
| [6] | Chen, Y.; Gross, J. L., Genus polynomials and crosscap-number polynomials for ring-like graphs, Math. Nachr., 292, 4, 760-776 (2019) · Zbl 1411.05124 |
| [7] | Chen, Y.; Gross, J. L.; Mansour, T.; Tucker, T. W., Genus polynomials of ladder-like sequences of graphs, J. Algebraic Comb., 52, 137-155 (2020) · Zbl 1453.05052 |
| [8] | Chen, Y.; Gross, J. L.; Mansour, T.; Tucker, T. W., Recurrences for the genus polynomials of linear sequences of graphs, Math. Slovaca, 70, 3, 505-526 (2020) · Zbl 1505.05046 |
| [9] | Feller, W., An Introduction to Probability Theory and Its Applications, Wiley Series in Probability and Statistics, vol. 2 (1971) · Zbl 0219.60003 |
| [10] | Gross, J. L.; Mansour, T.; Tucker, T. W., Log-concavity of genus distributions of ring-like families of graphs, Eur. J. Comb., 42, 74-91 (2014) · Zbl 1300.05079 |
| [11] | Gross, J. L.; Khan, I. F.; Mansour, T.; Tucker, T. W., Calculating genus polynomials via string operations and matrices, Ars Math. Contemp., 15, 267-295 (2018) · Zbl 1411.05066 |
| [12] | Gross, J. L.; Mansour, T.; Tucker, T. W.; Wang, David G. L., Log-concavity of combinations of sequences and applications to genus distributions, SIAM J. Discrete Math., 29, 2, 1002-1029 (2015) · Zbl 1314.05012 |
| [13] | Gross, J. L.; Mansour, T.; Tucker, T. W.; Wang, David G. L., Combinatorial conjectures that imply local log-concavity of graph genus polynomials, Eur. J. Comb., 52, 207-222 (2016) · Zbl 1327.05079 |
| [14] | Gross, J. L.; Mansour, T.; Tucker, T. W.; Wang, David G. L., Iterated claws have real-rooted genus polynomials, Ars Math. Contemp., 10, 2, 255-268 (2016) · Zbl 1347.05043 |
| [15] | Gross, J. L.; Robbins, D. P.; Tucker, T. W., Genus distributions for bouquets of circles, J. Comb. Theory, Ser. B, 47, 3, 292-306 (1989) · Zbl 0688.05038 |
| [16] | Gross, J. L.; Tucker, T. W., Topological Graph Theory (1987), Dover: Wiley, original edn. · Zbl 0621.05013 |
| [17] | Kwak, J. H.; Lee, J., Genus polynomials of dipoles, Kyungpook Math. J., 33, 115-125 (1995) · Zbl 0786.05045 |
| [18] | Khan, I. F.; Poshni, M. I.; Gross, J. L., Genus distribution of \(P_3 \square P_n\), Discrete Math., 312, 2863-2871 (2012) · Zbl 1248.05047 |
| [19] | Mohar, B., The genus distribution of doubly hexagonal chains, (Gutman, I., Topics in Chemical Graph Theory. Topics in Chemical Graph Theory, Mathematical Chemistry Monographs, vol. 16a (2014), Univ. Kragujevac: Univ. Kragujevac Kragujevac), 205-214 |
| [20] | Naulin, R.; Pabst, C., The roots of a polynomial depend continuously on its coefficients, Rev. Colomb. Mat., 28, 35-37 (1994) · Zbl 0819.12002 |
| [21] | Petrov, V. V., Limit Theorems of Probability Theory Sequences of Independent Random Variables (1995), Oxford University Press · Zbl 0826.60001 |
| [22] | Riper, R. G., The enumeration of graph embeddings (1987), Western Michigan University, Ph.D. Thesis |
| [23] | Ringel, G., Map Color Theorem (1974), Springer-Verlag · Zbl 0287.05102 |
| [24] | Stahl, S., The average genus of classes of graph embeddings, Congr. Numer., 40, 375-388 (1983) · Zbl 0532.05024 |
| [25] | Stahl, S., Permutation-partition pairs. III: embedding distributions of linear families of graphs, J. Comb. Theory, Ser. B, 52, 2, 191-218 (1991) · Zbl 0671.05032 |
| [26] | Stahl, S., On the average genus of the random graph, J. Graph Theory, 20, 1, 1-18 (1995) · Zbl 0840.05083 |
| [27] | Stahl, S., On the zeros of some genus polynomials, Can. J. Math., 49, 617-640 (1997) · Zbl 0879.05021 |
| [28] | Stahl, S., Region distributions of graph embedding and Stirling numbers, Discrete Math., 82, 57-76 (1990) · Zbl 0706.05027 |
| [29] | White, A. T., An introduction to random topological graph theory, Comb. Probab. Comput., 3, 04, 545-555 (1994) · Zbl 0815.05027 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
