Enumerative Problems Inspired by Mayer's Theory of Cluster Integrals

Abstract

The basic functional equations for connected and 2-connnected graphs can be traced back to the statistical physicists Mayer and Husimi. They play an essential role in establishing rigorously the virial expansion for imperfect gases. We first review these functional equations, putting the emphasis on the structural relationships between the various classes of graphs. We then investigate the problem of enumerating some classes of connected graphs all of whose 2-connected components (blocks) are contained in a given class $B$. Included are the species of Husimi graphs ($B =$ "complete graphs"), cacti ($B =$ "unoriented cycles"), and oriented cacti ($B =$ "oriented cycles"). For each of these, we address the question of their labelled and unlabelled enumeration, according (or not) to their block-size distributions. Finally we discuss the molecular expansion of these species. It consists of a descriptive classification of the unlabelled structures in terms of elementary species, from which all their symmetries can be deduced.