×

Study of exponential growth constants of directed heteropolygonal Archimedean lattices. (English) Zbl 1416.05122

Summary: We infer upper and lower bounds on the exponential growth constants \(\alpha (\Lambda )\), \(\alpha _0(\Lambda )\), and \(\beta (\Lambda )\) describing the large-\(n\) behavior of, respectively, the number of acyclic orientations, acyclic orientations with a unique source vertex, and totally cyclic orientations of arrows on bonds of several \(n\)-vertex heteropolygonal Archimedean lattices \(\Lambda\). These are, to our knowledge, the best bounds on these growth constants. The inferred upper and lower bounds on the growth constants are quite close to each other, which enables us to infer rather accurate estimates for the actual exponential growth constants. Our new results for heteropolygonal Archimedean lattices, combined with our recent results for homopolygonal Archimedean lattices, are consistent with the inference that the exponential growth constants \(\alpha (\Lambda )\), \(\alpha _0(\Lambda )\), and \(\beta (\Lambda )\) on these lattices are monotonically increasing functions of the lattice coordination number. Comparisons are made with the corresponding growth constants for spanning trees on these lattices. Our findings provide further support for the Merino-Welsh and Conde-Merino conjectures.

MSC:

05C20 Directed graphs (digraphs), tournaments
05C31 Graph polynomials
06B99 Lattices
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Chang, S.-C., Shrock, R.: Asymptotic behavior of acyclic and totally cyclic orientations of families of directed lattice graphs, arXiv:1810.07357 · Zbl 07457946
[2] Biggs, N.: Algebraic Graph Theory. Cambridge University Press, Cambridge, UK (1993)
[3] Welsh, D.J.A.: Complexity: Knots, Colourings, and Counting. Cambridge University Press, Cambridge (1993) · Zbl 0799.68008
[4] Bollobás, B.: Modern Graph Theory. Springer, New York (1998) · Zbl 0902.05016
[5] Chartrand, G., Lesniak, L.: Graphs and Digraphs. Chapman and Hall/CRC, New York (2005) · Zbl 1057.05001
[6] Grünbaum, B., Shephard, G.C.: Tilings and Patterns: An Introduction. Freeman, New York (1989) · Zbl 0746.52001
[7] For reviews of chromatic polynomials, see, e.g., R. C. Read and W. T. Tutte, “Chromatic Polynomials”, in Selected Topics in Graph Theory, 3, eds. L. W. Beineke and R. J. Wilson (Academic Press, New York, 1988), pp. 15-42 and F. M. Dong, K. M. Koh, and K. L. Teo, Chromatic Polynomials and Chromaticity of Graphs (World Scientific, Singapore, 2005)
[8] Stanley, R.P.: Acyclic orientations of graphs. Discrete Math. 5, 171-178 (1973) · Zbl 0258.05113
[9] Greene, C., Zaslavsky, T.: On the interpretation of Whitney numbers through arrangements of hyperplanes, zonotopes, non-Radon partitions, and orientations of graphs. Trans. Am. Math. Soc. 280, 97-126 (1983) · Zbl 0539.05024
[10] Tutte, W.T.: A contribution to the theory of chromatic polynomials. Can. J. Math. 6, 80-91 (1954) · Zbl 0055.17101
[11] Tutte, W.T.: On dichromatic polynomials. J. Comb. Theory 2, 301-320 (1967) · Zbl 0147.42902
[12] Brylawski, T.; Oxley, J.; White, N. (ed.), The Tutte polynomial and its applications, No. 40, 123-225 (1992), Cambridge · Zbl 0769.05026
[13] Welsh, D.J.A., Merino, C.: The Potts model and the Tutte polynomial. J. Math. Phys. 41, 1127-1152 (2000) · Zbl 1045.82501
[14] Gebhard, D.D., Sagan, B.E.: Sinks in acyclic orientations of graphs. J. Comb. Theory B 80, 130-146 (2000) · Zbl 1023.05069
[15] Merino, C., Welsh, D.J.A.: Forest, colorings, and acyclic orientations of the square lattice. Ann. Comb. 3, 417-429 (1999) · Zbl 0936.05043
[16] Calkin, N., Merino, C., Noble, S., Noy, M.: Improved bounds for the number of forests and acyclic orientations in the square lattice. Electron. J. Comb. 10(R4), 1-18 (2003) · Zbl 1020.05041
[17] Chang, S.-C., Shrock, R.: Tutte polynomials and related asymptotic limiting functions for recursive families of graphs (talk given by R. Shrock at Workshop on Tutte polynomials, Centre de Recerca Matemática (CRM), Sept. 2001, Univ. Autonoma de Barcelona), Adv. Appl. Math. 32, 44-87 (2004) · Zbl 1041.05027
[18] Las Vergnas, M.: Acyclic and totally cyclic orientations of combinatorial geometries. Discrete Math. 20, 51-61 (1977) · Zbl 0404.05017
[19] Las Vergnas, M.: Convexity in oriented matroids. J. Comb. Theory B 29, 231-243 (1980) · Zbl 0443.05026
[20] Biggs, N.L., Damerell, R.M., Sands, D.A.: Recursive families of graphs. J. Comb. Theory B 12, 123-131 (1972) · Zbl 0215.05504
[21] Beraha, S., Kahane, J., Weiss, N.: Limits of chromatic zeros of some families of maps. J. Comb. Theory B 28, 52-65 (1980) · Zbl 0433.05030
[22] Roček, M., Shrock, R., Tsai, S.-H.: Chromatic polynomials for families of strip graphs and their asymptotic limits. Phys. A 252, 505-546 (1998)
[23] Shrock, R., Tsai, S.-H.: Ground state degeneracy of Potts antiferromagnets on 2D lattices: approach using infinite cyclic strip graphs. Phys. Rev. E 60, 3512-3515 (1999)
[24] Shrock, R., Tsai, S.-H.: Exact partition functions for Potts antiferromagnets on cyclic lattice strips. Phys. A 275, 429-449 (2000)
[25] Shrock, R.: Exact Potts model partition functions on strip graphs. Phys. A 283, 388-446 (2000)
[26] Shrock, R., Tsai, S.-H.: Lower bounds and series for the ground state entropy of the Potts antiferromagnet on Archimedean lattices and their duals. Phys. Rev. E 56, 4111-4124 (1997)
[27] Chang, S.-C., Wang, W.: Spanning trees on lattices and integral identities. J. Phys. A 39, 10263-10275 (2006) · Zbl 1114.82014
[28] Shrock, R.: Chromatic polynomials and their zeros and asymptotic limits for families of graphs. Discrete Math. 231, 421-446 (2001) · Zbl 0973.05032
[29] Shrock, R., Tsai, S.-H.: Asymptotic limits and zeros of chromatic polynomials and ground state entropy of Potts antiferromagnets. Phys. Rev. E 55, 5165-5179 (1997)
[30] Shrock, R., Tsai, S.-H.: Upper and lower bounds for the ground state entropy of antiferromagnetic Potts models. Phys. Rev. E 55, 6791-6794 (1997)
[31] Shrock, R., Tsai, S.-H.: Ground state entropy of antiferromagnetic Potts models: bounds, series, and Monte Carlo measurements. Phys. Rev. E 56, 2733-2737 (1997)
[32] Chang, S.-C., Shrock, R.: Improved lower bounds on ground state entropy of the antiferromagnetic Potts model. Phys. Rev. E 91, 052142 (2015)
[33] Biggs, N.L.: Colouring square lattice graphs. Bull. Lond. Math. Soc. 9, 54-56 (1977) · Zbl 0352.05033
[34] Wu, F.Y.: Number of spanning trees on a lattice. J. Phys. A 10, L113-L115 (1977)
[35] Shrock, R., Wu, F.Y.: Spanning trees on graphs and lattices in \[d\] d dimensions. J. Phys. A 33, 3881-3902 (2000) · Zbl 0949.05041
[36] Chang, S.-C., Shrock, R.: Some exact results for spanning trees on lattices. J. Phys. A 39, 5653-5658 (2006) · Zbl 1122.82019
[37] Baxter, R.J.: Chromatic polynomials of large triangular lattices. J. Phys. A 20, 5241-5261 (1987) · Zbl 0625.05023
[38] Thomassen, C.: Spanning trees and orientations of graphs. J. Comb. 1, 101-111 (2010) · Zbl 1219.05044
[39] Conde, R., Merino, C.: Comparing the number of acyclic and totally cyclic orientations with that of spanning trees of a graph. Int. J. Math. Comb. 2, 79-89 (2009) · Zbl 1198.05015
[40] Merino, C., Ibañez, M., Guadalupe Rodrígez, M.: Guadalupe Rodrígez, a note on some inequalities for the Tutte polynomial of a matroid. Electron. Notes Direcrete Math. 34, 603-607 (2009) · Zbl 1273.05032
[41] Chávez-Lomeli, L.E., Merino, C., Noble, S.D., Ramírez-Ibáñez, M.: Some inequalities for the Tutte polynomial. Eur. J. Comb. 32, 422-433 (2011) · Zbl 1290.05055
[42] Noble, S.D., Royle, G.F.: The Merino-Welsh conjecture holds for series-parallel graphs. Eur. J. Comb. 38, 24-35 (2014) · Zbl 1282.05031
[43] Knauer, K., Martínez-Sandoval, L., Luis Ramírez-Alfonsín, J.: A Tutte polynomial inequality for lattice path matroids, arXiv:1510.00600 · Zbl 1377.05089
[44] Wu, F.Y.: The Potts model. Rev. Mod. Phys. 54, 235-268 (1982)
[45] Fortuin, C.M., Kasteleyn, P.W.: On the random cluster model. Physica 57, 536-564 (1972)
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.