The Potts model and chromatic functions of graphs

DOI10.4171/AIHPD/2MaRDI QIDQ2444869zbMATH OpenOpenAlexFDO

Authors Martin Klazar, Iain Moffatt, Martin Loebl

Publication date 11 April 2014

Published in Annales de l'Institut Henri Poincaré D. Combinatorics, Physics and their Interactions (AIHPD) (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1311.4348

zbMATH Keywords

\(U\)-polynomialchromatic polynomialgraph coloringgraph polynomialinteger partitionPotts model

Mathematics Subject Classification ID

Combinatorial aspects of partitions of integers (05A17) Coloring of graphs and hypergraphs (05C15) Graph polynomials (05C31) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20)

Abstract: The $U$-polynomial of Noble and Welsh is known to have intimate connections with the Potts model as well as with several important graph polynomials. For each graph $G$, $U(G)$ is equivalent to Stanley's symmetric bad colouring polynomial $XB(G)$. Moreover Sarmiento established the equivalence between $U$ and the polychromate of Brylawski. Loebl defined the $q$-dichromate $B_q(G,x,y)$ as a function of a graph $G$ and three independent variables $q,x,y$, proved that it is equal to the partition function of the Potts model with variable number of states and with a certain external field contribution, and conjectured that the $q$-dichromate is equivalent to the $U$-polynomial. He also proposed a stronger conjecture on integer partitions. The aim of this paper is two-fold. We present a construction disproving Loebl's integer partitions conjecture, and we introduce a new function $B_{r,q}(G;x,k)$ which is also equal to the partition function of the Potts model with variable number of states and with a (different) external field contribution, and we show that $B_{r,q}(G;x,k)$ is equivalent to the $U$-polynomial and to Stanley's symmetric bad colouring polynomial.

Review text

Summary: The \(U\)-polynomial of Noble and Welsh is known to have intimate connections with the Potts model as well as with several important graph polynomials. For each graph \(G\), \(U(G)\) is equivalent to the Stanley's symmetric bad colouring polynomial \(XB(G)\). Moreover Sarmiento established the equivalence between \(U\) and the polychromate of Brylawski. All these functions have countable number of variables, even though the restrictions to an arbitrary graph are honest polynomials. Loebl defined the \(q\)-dichromate \(B_q(G,x,y)\) as a function of graph \(G\) and three independent variables \(q\), \(x\), \(y\), proved that it is equal to the partition function of the Potts model with variable number of states and with certain magnetic field contribution, and conjectured that \(q\)-dichromate is equivalent to the \(U\)-polynomial. He also proposed a stronger conjecture on integer partitions. The aim of this paper is two-fold. We present a construction disproving the Loebl's integer partitions conjecture, and we introduce a new function \(B_{r,q}(G;x,k)\) which is also equal to the partition function of the Potts model with variable number of states and with a (different) external field contribution, and we show that \(B_{r,q}(G;x,k)\) is equivalent to \(U\)-polynomial. This gives a Potts model-type formulation for the \(U\)-polynomial.

Recommendations

• Potts model and graph theory.
• Exact results on Potts model partition functions in a generalized external field and weighted-set graph colorings
• Some exact results on the Potts model partition function in a magnetic field
• On the Potts model partition function in an external field
• Structural properties of Potts model partition functions and chromatic polynomials for lattice strips

Cites work

• A symmetric function generalization of the chromatic polynomial of a graph
• AN OVERVIEW OF Λ-TYPE OPERATIONS ON QUASI-SYMMETRIC FUNCTIONS
• Bounds on the complex zeros of (di)chromatic polynomials and Potts-model partition functions
• Chromatic polynomial, \(q\)-binomial counting and colored Jones function
• Graph colorings and related symmetric functions: ideas and applications: A description of results, interesting applications, and notable open problems.
• Intersection theory for graphs
• On the Potts model partition function in an external field
• The polychromate and a chord diagram polynomial
• The Tutte-Potts connection in the presence of an external magnetic field

Cited in

(6)

• Modular relations of the Tutte symmetric function
• Isomorphism of weighted trees and Stanley's isomorphism conjecture for caterpillars
• A vertex-weighted Tutte symmetric function, and constructing graphs with equal chromatic symmetric function
• Exact results on Potts model partition functions in a generalized external field and weighted-set graph colorings
• Link invariants, the chromatic polynomial and the Potts model
• Resolving Stanley's \(e\)-positivity of claw-contractible-free graphs

This page was built for publication: The Potts model and chromatic functions of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2444869)