Potts partition function and isomorphisms of weighted trees

Fonctions de partition de Potts et isomorphie d'arbres pondérés

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

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

We consider a question pertaining to the topic of graph reconstruction, which entertains links with the $W$-polynomial and (theoretical) statistical physics. Motivated by several open questions, we slightly deviate from the usual approaches to study, in the context of weighted trees, whether a given data (which can be obtained from the $W$-polynomial) distinguishes non-isomorphic weighted trees. We prove that this is the case if one restricts to any \emph{good class} of vertex-weighted trees. Good classes are rich: letting $\mathcal{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 $\mathcal{C}':=\left\{(T',w')\,:\,(T,w)\in \mathcal{C}\right\}$ is good and two elements $(A,b)$ and $(X,y)$ of $\mathcal{C}$ are isomorphic if and only if $(A',b')$ and $(X',y')$ are.

Nous considérons une question appartenant au domaine des reconstructions de graphes, et qui est reliée au polynôme $W$ ainsi qu'à des aspects (théoriques) de physique statistique. Motivés par plusieurs problèmes ouverts, nous dévions quelque peu des approches usuelles et étudions, dans le contexte des arbres pondérés, si la donnée de certaines informations (qui peuvent être déduites du polynômes $W$) permettent de distinguer des arbres non isomorphes. Nous démontrons que tel est le cas si l'on se restreint à n'importe quelle famille d'arbres qui vérifie certaines propriétés : nous appelons ces classes "bonnes". Les bonnes familles sont complexes, au sens suivant : en notant $\mathcal{C}$ la classe de tous les arbres dont les sommets sont pondérés, il est possible d'obtenir à partir de chaque arbre pondéré $(T,w)$ un autre arbre pondéré $(T',w')$ en temps polynomial, tel que $\mathcal{C}':=\left\{(T',w')\,:\,(T,w)\in \mathcal{C}\right\}$ est une bonne famille et deux éléments $(A,b)$ et $(X,y)$ de $\mathcal{C}$ sont isomorphes si, et seulement si, $(A',b')$ et $(X',y')$ le sont.

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

Domaines: Combinatoire [math.CO]

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