Evaluations of Tutte polynomials of regular graphs. (English) Zbl 1497.05126
Summary: Let \(T_G (x, y)\) be the Tutte polynomial of a graph \(G\). In this paper we show that if \((G_n)_n\) is a sequence of \(d\)-regular graphs with girth \(g(G_n) \to \infty\), then for \(x \geq 1\) and \(0 \leq y \leq 1\) we have
\[
\lim_{n \to \infty} T_{G_n} (x,y)^{1/v(G_n)} = t_d (x, y),
\]
where
\[
t_d (x, y) =
\begin{cases}
(d-1) \left(\frac{(d-1)^2}{(d-1)^2 -x}\right)^{d/2-1} & \text{if } x \leq d - 1 \text{ and} \\
& 0 \leq y \leq 1, \\
x \left(1+\frac{1}{x-1}\right)^{d/2-1} & \text{if } x > d - 1 \text{ and} \\
& 0 \leq y \leq 1.
\end{cases}
\]
If \((G_n )_n\) is a sequence of random \(d\)-regular graphs, then the same statement holds true asymptotically almost surely. This theorem generalizes results of B. D. McKay [in: Proceedings of the third Caribbean conference on combinatorics and computing, Cave Hill, Barbados, January 5–8, 1981. Cave Hill, Barbados: University of the West Indies, Department of Mathematics. 139–143 (1981; Zbl 0508.05054)] \((x = 1, y = 1\), spanning trees of random \(d\)-regular graphs) and R. Lyons [Comb. Probab. Comput. 14, No. 4, 491–522 (2005; Zbl 1076.05007)] \((x = 1, y = 1\), spanning trees of large-girth \(d\)-regular graphs). Interesting special cases are \(T_G (2, 1)\) counting the number of spanning forests, and \(T_G (2, 0)\) counting the number of acyclic orientations.
MSC:
| 05C31 | Graph polynomials |
References:
| [1] | Abért, Miklós; Csikvári, Péter; Frenkel, Péter; Kun, Gábor, Matchings in Benjamini-Schramm convergent graph sequences, Trans. Am. Math. Soc., 368, 6, 4197-4218 (2016) · Zbl 1331.05176 |
| [2] | Abért, Miklós; Csikvári, Péter; Hubai, Tamás, Matching measure, Benjamini-Schramm convergence and the monomer-dimer free energy, J. Stat. Phys., 161, 1, 16-34 (2015) · Zbl 1327.82034 |
| [3] | Abért, Miklós; Hubai, Tamás, Benjamini-Schramm convergence and the distribution of chromatic roots for sparse graphs, Combinatorica, 35, 2, 127-151 (2015) · Zbl 1363.05118 |
| [4] | Bandyopadhyay, Antar; Gamarnik, David, Counting without sampling: asymptotics of the log-partition function for certain statistical physics models, Random Struct. Algorithms, 33, 4, 452-479 (2008) · Zbl 1157.82006 |
| [5] | Bencs, Ferenc; Borbényi, Márton; Csikvári, Péter, Random cluster model on regular graphs (2022), arXiv preprint |
| [6] | Borbényi, Márton; Csikvári, Péter; Luo, Haoran, On the number of forests and connected spanning subgraphs (2020), arXiv preprint · Zbl 1479.05150 |
| [7] | Borgs, Christian; Chayes, Jennifer; Kahn, Jeff; Lovász, László, Left and right convergence of graphs with bounded degree, Random Struct. Algorithms, 42, 1, 1-28 (2013) · Zbl 1257.05172 |
| [8] | Brylawski, Thomas; Oxley, James, The Tutte polynomial and its applications, (Matroid Applications, vol. 40 (1992)), 123-225 · Zbl 0769.05026 |
| [9] | Cai, Jin-Yi, Holographic algorithms: guest column, ACM SIGACT News, 39, 2, 51-81 (2008) |
| [10] | Cai, Jin-yi; Chen, Xi, Complexity Dichotomies for Counting Problems: Volume 1, Boolean Domain (2017), Cambridge University Press · Zbl 1530.68006 |
| [11] | Cai, Jin-Yi; Lu, Pinyan, Holographic algorithms: the power of dimensionality resolved, (International Colloquium on Automata, Languages, and Programming (2007), Springer), 631-642 · Zbl 1171.68841 |
| [12] | Cai, Jin-Yi; Lu, Pinyan, On symmetric signatures in holographic algorithms, (Annual Symposium on Theoretical Aspects of Computer Science (2007), Springer), 429-440 · Zbl 1186.68540 |
| [13] | Cai, Jin-Yi; Lu, Pinyan, Basis collapse in holographic algorithms, Comput. Complex., 17, 2, 254-281 (2008) · Zbl 1149.68036 |
| [14] | Cai, Jin-Yi; Lu, Pinyan, Holographic algorithms: from art to science, J. Comput. Syst. Sci., 77, 1, 41-61 (2011) · Zbl 1214.68170 |
| [15] | Cai, Jin-Yi; Lu, Pinyan; Xia, Mingji, Holographic algorithms by Fibonacci gates and holographic reductions for hardness, (2008 49th Annual IEEE Symposium on Foundations of Computer Science (2008), IEEE), 644-653 |
| [16] | Chertkov, Michael; Chernyak, Vladimir Y., Loop calculus in statistical physics and information science, Phys. Rev. E, 73, 6, Article 065102 pp. (2006) · Zbl 1244.82058 |
| [17] | Chertkov, Michael; Chernyak, Vladimir Y., Loop series for discrete statistical models on graphs, J. Stat. Mech. Theory Exp., 2006, 06, Article P06009 pp. (2006) · Zbl 1244.82059 |
| [18] | Crapo, Henry H., The Tutte polynomial, Aequ. Math., 3, 3, 211-229 (1969) · Zbl 0197.50202 |
| [19] | Csikvári, Péter; Frenkel, Péter E., Benjamini-Schramm continuity of root moments of graph polynomials, Eur. J. Comb., 52, 302-320 (2016) · Zbl 1327.05159 |
| [20] | Dembo, Amir; Montanari, Andrea, Ising models on locally tree-like graphs, Ann. Appl. Probab., 20, 2, 565-592 (2010) · Zbl 1191.82025 |
| [21] | Dembo, Amir; Montanari, Andrea; Sly, Allan; Sun, Nike, The replica symmetric solution for Potts models on d-regular graphs, Commun. Math. Phys., 327, 2, 551-575 (2014) · Zbl 1288.82009 |
| [22] | Dembo, Amir; Montanari, Andrea; Sun, Nike, Factor models on locally tree-like graphs, Ann. Probab., 41, 6, 4162-4213 (2013) · Zbl 1280.05119 |
| [23] | Ellis-Monaghan, Joanna A.; Merino, Criel, Graph polynomials and their applications I: the Tutte polynomial, (Structural Analysis of Complex Networks (2011), Springer), 219-255 · Zbl 1221.05002 |
| [24] | Fortuin, Cees M.; Kasteleyn, Pieter W.; Ginibre, Jean, Correlation inequalities on some partially ordered sets, Commun. Math. Phys., 22, 2, 89-103 (1971) · Zbl 0346.06011 |
| [25] | Galanis, Andreas; Stefankovic, Daniel; Vigoda, Eric; Yang, Linji, Ferromagnetic Potts model: refined #BIS-hardness and related results, SIAM J. Comput., 45, 6, 2004-2065 (2016) · Zbl 1355.68198 |
| [26] | Godsil, Chris, Algebraic Combinatorics, vol. 6 (1993), CRC Press · Zbl 0784.05001 |
| [27] | Grimmett, Geoffrey R.; Winkler, Stephan N., Negative association in uniform forests and connected graphs, Random Struct. Algorithms, 24, 4, 444-460 (2004) · Zbl 1048.60007 |
| [28] | Heilmann, Ole J.; Lieb, Elliott H., Theory of monomer-dimer systems, (Statistical Mechanics (1972), Springer), 45-87 · Zbl 0228.05131 |
| [29] | Helmuth, Tyler; Jenssen, Matthew; Perkins, Will, Finite-size scaling, phase coexistence, and algorithms for the random cluster model on random graphs (2020), arXiv preprint |
| [30] | Lyons, Russell, Asymptotic enumeration of spanning trees (2002), arXiv preprint · Zbl 1076.05007 |
| [31] | McKay, Brendan D., Spanning trees in random regular graphs, (Proc. 3rd Car. Conf. Comb. and Comp. (1981), Citeseer), 139-143 · Zbl 0508.05054 |
| [32] | McKay, Brendan D., Spanning trees in regular graphs, Eur. J. Comb., 4, 2, 149-160 (1983) · Zbl 0517.05043 |
| [33] | McKay, Brendan D.; Wormald, Nicholas C.; Wysocka, Beata, Short cycles in random regular graphs, Electron. J. Comb., Article R66 pp. (2004) · Zbl 1063.05122 |
| [34] | Mohammadian, A., Laplacian matching polynomial of graphs, J. Algebraic Comb., 1-7 (2019) |
| [35] | Pemantle, Robin, Towards a theory of negative dependence, J. Math. Phys., 41, 3, 1371-1390 (2000) · Zbl 1052.62518 |
| [36] | Tutte, William Thomas, A contribution to the theory of chromatic polynomials, Can. J. Math., 6, 80-91 (1954) · Zbl 0055.17101 |
| [37] | Valiant, Leslie G., Expressiveness of matchgates, Theor. Comput. Sci., 289, 1, 457-471 (2002) · Zbl 1051.68064 |
| [38] | Valiant, Leslie G., Quantum circuits that can be simulated classically in polynomial time, SIAM J. Comput., 31, 4, 1229-1254 (2002) · Zbl 0997.81022 |
| [39] | Valiant, Leslie G., Accidental algorithms, (2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06) (2006), IEEE), 509-517 |
| [40] | Valiant, Leslie G., Holographic algorithms, SIAM J. Comput., 37, 5, 1565-1594 (2008) · Zbl 1152.05010 |
| [41] | Wainwright, Martin J.; Jaakkola, Tommi S.; Willsky, Alan S., Tree-based reparameterization framework for analysis of sum-product and related algorithms, IEEE Trans. Inf. Theory, 49, 5, 1120-1146 (2003) · Zbl 1063.68079 |
| [42] | Wan, Jiang-Chao; Wang, Yi; Mohammadian, Ali, On the location of zeros of the Laplacian matching polynomials of graphs (2021), arXiv preprint |
| [43] | Welsh, Dominic, The Tutte polynomial, Random Struct. Algorithms, 15, 3-4, 210-228 (1999) · Zbl 0934.05057 |
| [44] | Whitney, Hassler, A logical expansion in mathematics, Bull. Am. Math. Soc., 38, 8, 572-579 (1932) · Zbl 0005.14602 |
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.
