Asymptotic behavior of acyclic and cyclic orientations of directed lattice graphs. (English) Zbl 07457946

Chang, Shu-Chiuan; Shrock, Robert

Physica A 540, Article ID 123059, 35 p. (2020).

Summary: We calculate exponential growth constants describing the asymptotic behavior of several quantities enumerating classes of orientations of arrow variables on the bonds of several types of directed lattice strip graphs \(G\) of finite width and arbitrarily great length, in the infinite-length limit, denoted \(\{G\}\). Specifically, we calculate the exponential growth constants for (i) acyclic orientations, \(\alpha(\{G\})\), (ii) acyclic orientations with a single source vertex, \(\alpha_0(\{G\})\), and (iii) totally cyclic orientations, \(\beta(\{G\})\). We consider several lattices, including square (\(sq\)), triangular (\(tri\)), and honeycomb (\(hc\)). From our calculations, we infer lower and upper bounds on these exponential growth constants for the respective infinite lattices. To our knowledge, these are the best current bounds on these quantities. Since our lower and upper bounds are quite close to each other, we can infer very accurate approximate values for the exponential growth constants, with fractional uncertainties ranging from \(O(10^{-4})\) to \(O(10^{-2})\). Further, we present exact values of \(\alpha(tri)\), \(\alpha_0(tri)\), and \(\beta(hc)\) and use them to show that our lower and upper bounds on these quantities are very close to these exact values, even for modest strip widths. Results are also given for a nonplanar lattice denoted \(sq_d\). We show that \(\alpha(\{G\})\), \(\alpha_0(\{G\})\), and \(\beta(\{G\})\) are monotonically increasing functions of vertex degree for these lattices. A comparison is given of these exponential growth constants with the corresponding exponential growth constant \(\tau(\{G\})\) for spanning trees. Our results are in agreement with inequalities following from the Merino-Welsh and Conde-Merino conjectures.

MSC:

82-XX

Statistical mechanics, structure of matter

References:

[1]	Biggs, N., Algebraic Graph Theory (1993), Cambridge Univ. Press: Cambridge Univ. Press Cambridge, UK; Welsh, D. J.A., Complexity: Knots, Colourings, and Counting (1993), Cambridge Univ. Press: Cambridge Univ. Press Cambridge, UK; Bollobás, B., Modern Graph Theory (1998), Springer: Springer New York; Chartrand, G.; Lesniak, L., Graphs and Digraphs (2005), Chapman and Hall/CRC: Chapman and Hall/CRC New York · Zbl 0799.68008
[2]	Birkhoff, G. D., A determinant formula for the number of ways of coloring a map, Ann. of Math., 14, 42-46 (1912) · JFM 43.0574.02
[3]	Whitney, H., The coloring of graphs, Ann. of Math., 33, 688-718 (1932) · JFM 58.0606.01
[4]	Birkhoff, G. D.; Lewis, D. C., Chromatic polynomials, Trans. Amer. Math. Soc., 60 (1946), 355-451 · Zbl 0060.41601
[5]	Read, R. C.; Tutte, W. T., Chromatic polynomials, (Beineke, L. W.; Wilson, R. J., Selected Topics in Graph Theory, Vol. 3 (1988), Academic Press: Academic Press New York), 15-42 · Zbl 0667.05022
[6]	Dong, F. M.; Koh, K. M.; Teo, K. L., Chromatic Polynomials and Chromaticity of Graphs (2005), World Scientific: World Scientific Singapore · Zbl 1070.05038
[7]	Stanley, R. P., Acyclic orientations of graphs, Discrete Math., 5, 171-178 (1973) · Zbl 0258.05113
[8]	Wu, F. Y., The potts model, Rev. Modern Phys., 54, 235-268 (1982)
[9]	Tutte, W. T., A contribution to the theory of chromatic polynomials, Canad. J. Math., 6, 80-91 (1954) · Zbl 0055.17101
[10]	Tutte, W. T., On dichromatic polynomials, J. Combin. Theory, 2, 301-320 (1967) · Zbl 0147.42902
[11]	Brylawski, T.; Oxley, J., The Tutte polynomial and its applications, (White, N., Matroid Applications. Matroid Applications, Encyclopedia of Mathematics and its Applications, vol. 40 (1992), Cambridge Univ. Press: Cambridge Univ. Press Cambridge, UK), 123-225 · Zbl 0769.05026
[12]	Welsh, D. J.A.; Merino, C., The Potts model and the Tutte polynomial, J. Math. Phys., 41, 1127-1152 (2000) · Zbl 1045.82501
[13]	Beaudin, L.; Ellis-Monaghan, J.; Pangborn, G.; Shrock, R., A little statistical mechanics for the graph theorist, Discrete Math., 310, 2037-2053 (2010) · Zbl 1223.05125
[14]	Ellis-Monaghan, J.; Merino, C., Graph polynomials and their applications I: The Tutte polynomial, (Dehmer, M., Structural Analysis of Complex Networks (2011), Birkhauser: Birkhauser Boston), 219-255 · Zbl 1221.05002
[15]	Greene, C.; Zaslavsky, T., On the interpretation of Whitney numbers through arrangements of hyperplanes, zonotopes, non-radon partitions, and orientations of graphs, Trans. Amer. Math. Soc., 280, 97-126 (1983) · Zbl 0539.05024
[16]	Gebhard, D. D.; Sagan, B. E., Sinks in acyclic orientations of graphs, J. Combin. Theory Ser. B, 80, 130-146 (2000) · Zbl 1023.05069
[17]	Las Vergnas, M., Acyclic and totally cyclic orientations of combinatorial geometries, Discrete Math., 20, 51-61 (1977) · Zbl 0404.05017
[18]	Las Vergnas, M., Convexity in oriented matroids, J. Combin. Theory Ser. B, 29, 231-243 (1980) · Zbl 0443.05026
[19]	Merino, C.; Welsh, D. J.A., Forest, colorings, and acyclic orientations of the square lattice, Ann. Combin., 3, 417-429 (1999) · Zbl 0936.05043
[20]	Calkin, N.; Merino, C.; Noble, S.; Noy, M., Improved bounds for the number of forests and acyclic orientations in the square lattice, Electron. J. Combin., 10, R4, 1-18 (2003) · Zbl 1020.05041
[21]	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
[22]	Chang, S.-C., Acyclic orientations on the Sierpinski gasket, Internat. J. Modern Phys. B, 26, Article 1250128 pp. (2012) · Zbl 1274.28011
[23]	Mani, A. P., On some tutte polynomial sequences in the square lattice, J. Combin. Theory Ser. B, 102, 436-453 (2012) · Zbl 1239.05097
[24]	Garijo, D.; Gegúndez, M. E.; Márquez, A.; Revuelta, M. P.; Sagols, F., Computing the Tutte polynomial of Archimedean tilings, Appl. Math. Comput., 242, 842-855 (2014) · Zbl 1334.52018
[25]	Biggs, N. L.; Damerell, R. M.; Sands, D. A., Recursive families of graphs, J. Combin. Theory Ser. B, 12, 123-131 (1972) · Zbl 0215.05504
[26]	Biggs, N. L., Colouring square lattice graphs, Bull. Lond. Math. Soc., 9, 54-56 (1977) · Zbl 0352.05033
[27]	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)
[28]	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)
[29]	Roček, M.; Shrock, R.; Tsai, S.-H., Chromatic polynomials for families of strip graphs and their asymptotic limits, Physica A, 252, 505-546 (1998)
[30]	Shrock, R.; Tsai, S.-H., Ground state entropy of Potts antiferromagnets on homeomorphic families of strip graphs, Physica A, 259, 315-348 (1998)
[31]	Shrock, R.; Tsai, S.-H., Ground-state entropy of the Potts antiferromagnet on cyclic strip graphs, J. Phys. A, 32, L195-L200 (1999) · Zbl 0946.82012
[32]	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)
[33]	Shrock, R.; Tsai, S.-H., Exact partition functions for Potts antiferromagnets on cyclic lattice strips, Physica A, 275, 429-449 (2000)
[34]	Shrock, R., \( T = 0\) Partition functions for potts antiferromagnets on Möbius strips and effects of graph topology, Phys. Lett. A, 261, 57-62 (1999) · Zbl 0955.82012
[35]	Shrock, R., Chromatic polynomials and their zeros and asymptotic limits for families of graphs, Discrete Math., 231, 421-446 (2001) · Zbl 0973.05032
[36]	Biggs, N. L.; Shrock, R., \( T = 0\) Partition functions for Potts antiferromagnets on square lattice strips with (twisted) periodic boundary conditions, J. Phys. A (Letts), 32, L489-L493 (1999) · Zbl 0958.82006
[37]	Chang, S.-C.; Shrock, R., Ground-state entropy of the Potts antiferromagnet with next-nearest-neighbor spin-spin couplings on strips of the square lattice, Phys. Rev. E, 62, 4650-4664 (2000)
[38]	Chang, S.-C.; Shrock, R., Ground state entropy of the Potts antiferromagnet on triangular lattice strips, Ann. Phys., 290, 124-155 (2001) · Zbl 1046.82505
[39]	Shrock, R., Exact Potts model partition functions for ladder graphs, Physica A, 283, 388-446 (2000)
[40]	Chang, S.-C.; Shrock, R., Exact Potts model partition functions on strips of the triangular lattice, Physica A, 286, 189-238 (2000) · Zbl 1052.82513
[41]	Chang, S.-C.; Shrock, R., \( T = 0\) Partition functions for Potts Antiferromagnets on lattice strips with fully periodic boundary conditions, Physica A, 292, 307-345 (2001) · Zbl 0972.82032
[42]	Chang, S.-C.; Shrock, R., Exact Potts model partition functions on strips of the honeycomb lattice, Physica A, 296, 183-233 (2001) · Zbl 0978.82020
[43]	Chang, S.-C.; Shrock, R., Exact partition function for the Potts model with next-nearest-eighbor couplings on strips of the square lattice, Internat. J. Modern Phys. B, 15, 443-478 (2001) · Zbl 1192.82019
[44]	Chang, S.-C.; Shrock, R., Exact Potts model partition functions on wider arbitrary-length strips of the square lattice, Physica A, 296, 234-288 (2001) · Zbl 0978.82021
[45]	Chang, S.-C.; Shrock, R., Potts model partition functions for self-dual families of graphs, Physica A, 301, 301-329 (2001) · Zbl 0978.82024
[46]	Chang, S.-C.; Shrock, R., Complex-temperature phase diagrams for the \(q\)-state Potts model on self-Dual families of graphs and the nature of the \(q \to \infty\) limit, Phys. Rev. E, 64, Article 066116 pp. (2001)
[47]	Biggs, N. L.; Meredith, G. H.J., Approximations for chromatic polynomials, J. Combin. Theory Ser. B, 20, 5-19 (1976) · Zbl 0283.05102
[48]	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)
[49]	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)
[50]	Baxter, R. J., \(q\) Colourings of the triangular lattice, J. Phys. A: Math. Gen., 19, 2821-2839 (1986); Baxter, R. J., Chromatic polynomials of large triangular lattices, J. Phys. A: Math. Gen., 20, 5241-5261 (1987) · Zbl 0625.05023
[51]	Chang, S.-C.; Shrock, R., Study of exponential growth constants of directed heteropolygonal archimedean lattices, J. Stat. Phys., 174, 1288-1315 (2019) · Zbl 1416.05122
[52]	Wu, F. Y., Number of spanning trees on a lattice, J. Phys. A, 10, L113-L115 (1977)
[53]	Shrock, R.; Wu, F. Y., Spanning trees on graphs and lattices in \(d\) dimensions, J. Phys. A, 33, 3881-3902 (2000) · Zbl 0949.05041
[54]	Chang, S.-C.; Shrock, R., Some exact results for spanning trees on lattices, J. Phys. A, 39, 5653-5658 (2006) · Zbl 1122.82019
[55]	Chang, S.-C.; Wang, W., Spanning trees on lattices and integral identities, J. Phys. A, 39, 10263-10275 (2006) · Zbl 1114.82014
[56]	Thomassen, C., Spanning trees and orientations of graphs, J. Combin., 1, 101-111 (2010) · Zbl 1219.05044
[57]	Conde, R.; Merino, C., Comparing the number of acyclic and totally cyclic orientations with that of spanning trees of a graph, Int. J. Math. Combin., 2, 79-89 (2009) · Zbl 1198.05015
[58]	Merino, C.; Ibañez, M.; Guadalupe Rodrígo, M., A note on some inequalities for the Tutte polynomial of a matroid, Electron. Notes Discrete Math., 34, 603-607 (2009) · Zbl 1273.05032
[59]	Chávez-Lomeli, L. E.; Merino, C.; Noble, S. D.; Ramírez-Ibáñez, M., Some inequalities for the Tutte polynomial, European J. Combin., 32, 422-433 (2011) · Zbl 1290.05055
[60]	Noble, S. D.; Royle, G. F., The Merino-Welsh conjecture holds for series-parallel graphs, European J. Combin., 38, 24-35 (2014) · Zbl 1282.05031
[61]	Knauer, K.; Martínez-Sandoval, L.; Luis Ramírez-Alfonsín, J., A tutte polynomial inequality for lattice path matroids, Adv. Appl. Math., 94, 23-38 (2018) · Zbl 1377.05089
[62]	Fortuin, C. M.; Kasteleyn, P. W., On the random cluster model, Physica, 57, 536-564 (1972)