The bivariate Ising polynomial of a graph. (English) Zbl 1211.05059
Summary: We discuss the two variable Ising polynomials in a graph theoretical setting. This polynomial has its origin in physics as the partition function of the Ising model with an external field. We prove some basic properties of the Ising polynomial and demonstrate that it encodes a large amount of combinatorial information about a graph. We also give examples which prove that certain properties, such as the chromatic number, are not determined by the Ising polynomial. Finally we prove that there exist large families of non-isomorphic planar triangulations with identical Ising polynomial.
MSC:
| 05C31 | Graph polynomials |
| 82B20 | Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics |
References:
| [1] | Bollobás, B.; Pebody, L.; Riordan, O., Contraction-deletion invariants for graphs, J. Combin. Theory Ser. B, 80, 2, 320-345 (2000) · Zbl 1024.05028 |
| [2] | Fortuin, C. M.; Kasteleyn, P. W., On the random-cluster model. I. Introduction and relation to other models, Physica, 57, 536-564 (1972) |
| [3] | Freedman, M.; Lovász, L.; Schrijver, A., Reflection positivity, rank connectivity, and homomorphism of graphs, J. Amer. Math. Soc., 20, 1, 37-51 (2007), electronic · Zbl 1107.05089 |
| [4] | Gao, Z.; Wormald, N. C., Asymptotic normality determined by high moments, and submap counts of random maps, Probab. Theory Related Fields, 130, 3, 368-376 (2004) · Zbl 1058.60015 |
| [5] | Godsil, C. D., Algebraic combinatorics (1993), Chapman & Hall: Chapman & Hall New York, Chapter 2 · Zbl 0814.05075 |
| [6] | Grimmett, G., The random-cluster model, (Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 333 (2006), Springer-Verlag: Springer-Verlag Berlin) · Zbl 0858.60093 |
| [7] | Ising, E., Beitrag zur Theorie des Ferromagnetismus, Z. Physik, 31, 253-258 (1925) · Zbl 1439.82056 |
| [8] | Lee, T. D.; Yang, C. N., Statistical theory of equations of state and phase transitions. II. Lattice gas and Ising model, Physical Rev. (2), 87, 410-419 (1952) · Zbl 0048.43401 |
| [9] | Lundow, Per Håkan; Markström, Klas, Exact and approximate compression of transfer matrices for graph homomorphisms, LMS J. Comput. Math., 11, 1-14 (2008) · Zbl 1223.05177 |
| [10] | McKay, B. D., On the spectral characterisation of trees, Ars Combinatoria, 3, 219-232 (1977) · Zbl 0404.05045 |
| [11] | Noy, M., Graphs determined by polynomial invariants, Theoret. Comput. Sci., 307, 2, 365-384 (2003), Random generation of combinatorial objects and bijective combinatorics · Zbl 1048.05072 |
| [12] | Read, R. C.; Tutte, W. T., Chromatic polynomials, (Selected topics in graph theory, 3 (1988), Academic Press: Academic Press San Diego, CA), 15-42 · Zbl 0667.05022 |
| [13] | Reed, B. A., Algorithmic aspects of tree width, (Recent advances in algorithms and combinatorics. Recent advances in algorithms and combinatorics, CMS Books Math./Ouvrages Math. SMC, vol. 11 (2003), Springer: Springer New York), 85-107 · Zbl 1035.05090 |
| [14] | Richmond, L. B.; Wormald, N. C., Almost all maps are asymmetric, J. Combin. Theory Ser. B, 63, 1, 1-7 (1995) · Zbl 0820.05017 |
| [15] | Richmond, L. Bruce; Wormald, Nicholas C., Random triangulations of the plane, European J. Combin., 9, 1, 61-71 (1988) · Zbl 0663.05059 |
| [16] | Scott, A. D.; Sokal, A. D., The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma, J. Stat. Phys., 118, 5-6, 1151-1261 (2005) · Zbl 1107.82013 |
| [17] | Scott, A. D.; Sokal, A. D., On dependency graphs and the lattice gas, Combin. Probab. Comput., 15, 1-2, 253-279 (2006) · Zbl 1138.05323 |
| [18] | Sokal, A. D., The multivariate Tutte polynomial (alias Potts model) for graphs and matroids, (Surveys in combinatorics 2005. Surveys in combinatorics 2005, London Math. Soc. Lecture Note Ser., vol. 327 (2005), Cambridge Univ. Press: Cambridge Univ. Press Cambridge), 173-226 · Zbl 1110.05020 |
| [19] | Tutte, W. T., A ring in graph theory, Proc. Cambridge Philos. Soc., 43, 26-40 (1947) · Zbl 0031.41803 |
| [20] | Tutte, W. T., Graph theory as I have known it, (Oxford Lecture Series in Mathematics and its Applications, vol. 11 (1998), The Clarendon Press Oxford University Press: The Clarendon Press Oxford University Press New York), With a foreword by U. S. R. Murty. · Zbl 0614.05054 |
| [21] | van der Waerden, B. L., Die lange reichweite der regelmassigen atomanordnung in mischkristallen, Zeitschrift fur Physik, 118, 473 (1941) · Zbl 0026.28301 |
| [22] | Welsh, D. J.A., Complexity: knots, colourings and counting, (London Mathematical Society Lecture Note Series, vol. 186 (1993), Cambridge University Press: Cambridge University Press Cambridge) · Zbl 0799.68008 |
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.
