Potts partition function and isomorphisms of trees

Martin Loebl (1) , Jean-Sébastien Sereni (2)

1 KAM - Department of Applied Mathematics (KAM)
2 ORPAILLEUR - Knowledge representation, reasonning

We explore the well-known Stanley conjecture stating that the symmetric chromatic polynomial distinguishes non-isomorphic trees. The graph isomorphism problem has been extensively studied for decades. There are strong algorithmic advances, but our research concentrates on the following question: is there a natural function on graphs that decides graph isomorphism? Curiously, in mathematics and in physics the concepts of a ''natural'' graph function bear strong similarities: it essentially means that the function comes from the Tutte polynomial, which in physics is called the Potts partition function. Somewhat surprisingly, after decades of study, this bold project is still not infirmed. The aim of our research is to present a result that supports the project: we prove that the Stanley isomorphism conjecture holds for every good class of vertex-weighted trees. Good classes are rich: letting C be the class of all vertex-weighted trees, one can obtain for each weighted tree (T,w) a weighted tree (T',w') in polynomial time, so that C':={(T',w') | (T,w) ∈ C} is good and two elements (A,b) and (X,y) of C are isomorphic if and only if (A',b') and (X',y') are.

Mots clés: U-polynomial; tree; graph isomorphism; graph reconstruction; Stanley's conjecture

Domaines: Combinatoire [math.CO]

Martin Loebl, Jean-Sébastien Sereni. Potts partition function and isomorphisms of trees. [Research Report] Loria & Inria Grand Est. 2014. ⟨hal-00992104v1⟩