Séminaire Lotharingien de Combinatoire 61A (2009), Article B61Af

MAYER AND REE–HOOVER WEIGHTS OF INFINITE FAMILIES OF 2-CONNECTED GRAPHS

AMEL KAOUCHE AND PIERRE LEROUX

Abstract. We study graph weights (i.e., graph invariants) which arise naturally in Mayer’s theory and Ree–Hoover’s theory of virial expansions in the context of a non-ideal gas. We give special attention to the Second Mayer weight w_{M}(c) and the Ree–Hoover weight w_{RH}(c) of a 2-connected graph c which arise from the hard-core continuum gas in one dimension. These weights are computed using signed volumes of convex polytopes naturally associated with the graph c. Among our results are explicit formulas for the values of Mayer weights and Ree–Hoover weights for certain infinite families of 2-connected graphs.

Résumé. Nous étudions des poids de graphes (à savoir, des invariants de graphes) qui apparaissent naturellement dans les théories de Mayer et de Ree– Hoover du développement du viriel dans le contexte de gas non-idéaux. Nous nous intéressons spécialement au second poids de Mayer w_{M}(c) et de Ree– Hoover w_{RH}(c) pour un graphe 2-connexe c provenant d’un gaz à noyaux durs en dimension un. Ces poids sont calculés en utilisant des volumes signés de polytopes convexes associés au graphe c. Parmi nos résultats, nous donnons des formules explicites pour le poids de Mayer et de Ree–Hoover pour certaines familles infinies de graphes 2-connexes.

1. Introduction

Graph weights can be defined as functions on (simple, finite) graphs taking scalar or polynomial values and which are invariant under isomorphism, i.e., under vertex relabelling. Since most graphical concepts share this invariance property, examples of graph weights abound. For instance, the graph complexity γ(g) of a graph g, which is defined as the number of maximal spanning forests of g, is an example of a graph weight. In the context of a non-ideal gas in a vessel V ⊆ ℝ^{d}, the Second Mayer weight w_{M}(c) of a connected graph c, over the set [n] = {1, 2, …, n} of vertices, is defined by

w_{M}(c) = ∫_{(ℝ^{d})^{n−1}} ∏_{\{i,j\}∈c} f(∥\overrightarrow{x_{i}} − \overrightarrow{x_{j}}∥) d\overrightarrow{x_{1}} ⋯ d\overrightarrow{x_{n−1}}, \overrightarrow{x_{n}} = 0,  (1)

where \overrightarrow{x_{1}}, …, \overrightarrow{x_{n}} are variables in ℝ^{d} representing the positions of n particles in V (V → ∞), the value \overrightarrow{x_{n}} = 0 being arbitrarily fixed, and where f = f(r) is realvalued function associated with the pairwise interaction potential of the particles, see [16, 7].

Let C[n] be the set of connected graphs over [n]. The total sum of weights of connected graphs over [n] is denoted by

|C[n]|_{w_{M}} = ∑_{c∈C[n]} w_{M}(c).  (2)

The interest of this sequence in statistical mechanics comes from the fact that the pressure P of the system is given by its exponential generating function as follows (see [7]):

\frac{P}{kT} = C_{w_{M}} (z) = ∑_{n≥1} |C[n]|_{w_{M}} \frac{z^{n}}{n!} ,  (3)

where k is a constant, T is the temperature and z is a variable called the fugacity or the activity of the system. It is known that the weight w_{M} is multiplicative over 2-connected components so that in order to compute the weights w_{M}(c) of the connected graphs c ∈ C[n], it is sufficient to compute the weights w_{M}(b) for 2-connected graphs b ∈ B[n] (B for blocks). Moreover, these occur in the so-called virial expansion proposed by Kamerlingh Onnes in 1901

\frac{P}{kT} = ρ + β_{2}ρ^{2} + β_{3}ρ^{3} + ⋯,  (4)

where ρ is the density. Indeed, it can be shown that

β_{n} = \frac{1 − n}{n!}|B[n]|_{w_{M}} ,  (5)

where B[n] denote the set of 2-connected graphs over [n] and |B[n]|_{w_{M}} is the total sum of weights of 2-connected graphs over [n]. In order to compute this expansion numerically, Ree and Hoover [10] introduced a modified weight denoted by w_{RH}(b), for 2-connected graphs b, which greatly simplifies the computations. It is defined by

w_{RH}(b) = ∫_{(ℝ^{d})^{n−1}} ∏_{\{i,j\}∈b} f(∥\overrightarrow{x_{i}} − \overrightarrow{x_{j}}∥) ∏_{\{i,j\}∉b} \overline{f}(∥\overrightarrow{x_{i}} − \overrightarrow{x_{j}}∥) d\overrightarrow{x_{1}} ⋯ d\overrightarrow{x_{n−1}}, \overrightarrow{x_{n}} = 0,

(6)

where \overline{f}(r) = 1 + f(r). Using this new weight, Ree and Hoover [10, 11, 12] and later Clisby and McCoy [2, 3] have computed the virial coefficients β_{n}, for n up to 10, in dimensions d ≤ 8, in the case of the hard-core continuum gas, that is when the interaction is given by

f(r) = −χ(r < 1), \overline{f}(r) = χ(r ≥ 1),  (7)

where χ denotes the characteristic function (χ(P) = 1, if P is true and 0, otherwise).

While physicists are interested in summing the weights of all connected or 2connected graphs of a given order, the present paper focuses on individual graph contributions and their combinatorial significance. For a given individual graph, the Mayer and Ree–Hoover weights can be computed using Ehrhart polynomials in the case of the hard-core continuum gas in dimension d = 1. This has been done systematically for graphs of size ≤ 8 in [5, 6]. The main goal of the present paper is to give exact formulas for certain infinite families of graphs.

In Section 1, we use Möbius inversion to give explicit linear relations expressing the Ree–Hoover weights in terms of the Mayer weights and vice versa. The total Mayer weight |B[n]|_{w_{M}} is then rewritten in terms of the weight function w_{RH} introduced by Ree and Hoover [10, 11]. This rewriting involves special coefficients called star contents. The interest of using the Ree–Hoover weight is that it has the value zero for many graphs. Some general explicit and recursive properties of the star content are given.

Section 2 is devoted to the special case of the hard-core continuum gas in one dimension in which the Mayer weight turns out to be a signed volume of a convex polytope P(c) naturally associated with the graph c. Sufficient conditions for the nullity of the Ree–Hoover weight of a graph are also given. An alternate useful tool, a decomposition of the polytope P(c) into a certain number of (n − 1)-dimensional simplices, of volume 1/(n − 1)! is exploited. This method was introduced in [7] and is called the method of graph homomorphisms. We adapt this method to the context of Ree–Hoover weights. The explicit computation of Mayer or Ree–Hoover weights of particular graphs is very difficult in general and have been made for only certain specific families of graphs (e.g., the complete graphs K_{n}, the cycle graphs C_{n}). In the present paper we extend this list to graphs of the form K_{n}\g, where g can be a star graph, a cycle, path graph, or connections of some of these graphs, etc. We give new explicit formulas of the Ree–Hoover weight of these graphs in Section 3. Section 4 is devoted to the explicit computation of their Mayer weight.

The following conventions are used in the present paper. Each graph g is identified with its set of edges. So that, {i, j} ∈ g means that {i, j} is an edge in g between vertex i and vertex j. The number of edges in g is denoted e(g). If e is an edge of g (i.e. e ∈ g), g\e denotes the graph obtained from g by removing the edge e. If a is a vertex of g, g\a denotes the graph obtained by removing from g vertex a and all its incident edges. If b and d are graphs, b ⊆ d means that b is a subgraph of d. The complete graph on the vertex set [n] = {1, 2, …, n} is denoted by K_{n}. The complementary graph of a subgraph g ⊆ K_{n} is the graph \overline{g} = K_{n}\g.

Acknowledgements. The first author would like to acknowledge particularly one referee for his valuable suggestions for the improvement of the paper, and Gilbert Labelle and Cédric Lamathe for their help.

2. Relations between w_{M} and w_{RH}

2.1. Mayer weight, Ree–Hoover weight and star content. An important rewriting of the virial coefficients was performed by Ree and Hoover [10, 11] by introducing the function

\overline{f}(r) = 1 + f(r)  (8)

and defining a new weight (denoted here by w_{RH}(b)) for 2-connected graphs b, by (9)

w_{RH}(b) = ∫_{(ℝ^{d})^{n−1}} ∏_{\{i,j\}∈b} f(∥\overrightarrow{x_{i}} − \overrightarrow{x_{j}}∥) ∏_{\{i,j\}∉b} \overline{f}(∥\overrightarrow{x_{i}} − \overrightarrow{x_{j}}∥) d\overrightarrow{x_{1}} ⋯ d\overrightarrow{x_{n−1}}, \overrightarrow{x_{n}} = 0,

(9)

and then expanding each weight w_{M}(b) by substituting 1 = \overline{f} − f for pairs of vertices not connected by edges. Upon performing this rewriting of the Mayer weights series, vertices in the resultant graphs will all be mutually connected by either f bonds (solid lines) or\overline{f} bonds (dotted lines). For example, we have

w_{M}( ) = w_{RH}( ),  (10)
w_{M}( ) = w_{RH}( ) − w_{RH}( ),  (11)

w_{M}( ) = w_{MRH}( ) − w_{M}( )
= {w_{RH}( ) − w_{RH}( )} − {w_{RH}( ) − w_{RH}( )}
= w_{RH}( ) − 2 · w_{RH}( ) + w_{RH}( ).  (12)

In the general situation, using Möbius inversion, it is easy to state formulas linking the two weights w_{M} and w_{RH}. These formulas are implicit in the work of [11].

Proposition 1. For a 2-connected graph b, we have

w_{RH}(b) = ∑_{b⊆d⊆K_{n}} w_{M}(d),  (13)
w_{M}(b) = ∑_{b⊆d⊆K_{n}}(−1)^{e(d)−e(b)}w_{RH}(d).  (14)

Proof. From (9) and the fact that \overline{f} = 1 + f, we have

w_{RH}(b) = ∫_{(ℝ^{d})^{n−1}} ∏_{\{i,j\}∈b} f(∥\overrightarrow{x_{i}} − \overrightarrow{x_{j}}∥) ∏_{\{i,j\}∉b} \overline{f}(∥\overrightarrow{x_{i}} − \overrightarrow{x_{j}}∥) d\overrightarrow{x_{1}} ⋯ d\overrightarrow{x_{n−1}}

= ∫_{(ℝ^{d})^{n−1}} ∏_{\{i,j\}∈b} f(∥\overrightarrow{x_{i}} − \overrightarrow{x_{j}}∥) ∏_{\{i,j\}∈\overline{b}}(1 + f(∥\overrightarrow{x_{i}} − \overrightarrow{x_{j}}∥)) d\overrightarrow{x_{1}} ⋯ d\overrightarrow{x_{n−1}}

= ∫_{(ℝ^{d})^{n−1}} ∑_{E⊆\overline{b}} ∏_{\{i,j\}∈E∪b} f(∥\overrightarrow{x_{i}} − \overrightarrow{x_{j}}∥) d\overrightarrow{x_{1}} ⋯ d\overrightarrow{x_{n−1}}

= ∫_{(ℝ^{d})^{n−1}} ∑_{b⊆d⊆K_{n}} ∏_{\{i,j\}∈d} f(∥\overrightarrow{x_{i}} − \overrightarrow{x_{j}}∥) d\overrightarrow{x_{1}} ⋯ d\overrightarrow{x_{n−1}}

= ∑_{b⊆d⊆K_{n}} w_{M}(d).

Using Möbius inversion on (13) for the lattice of subsets of K_{n}, with the Möbius function μ(b, d) = (−1)^{e(d)−e(b)}, we find (14). □

Remark 1. By the definition of the Ree–Hoover weight, we have in particular

w_{RH}(K_{n}) = w_{M}(K_{n}), n ≥ 2.  (15)

When expressing the total weight |B[n]|_{w_{M}} in terms of Ree–Hoover weights, there is a new factor which appears for each graph in the expansion of each Mayer weight w_{M}(b). This factor is called the star content by Ree and Hoover [11], and may be either a positive or negative integer.

Definition 2. Let d be a 2-connected graph over the set [n] = {1, 2, ⋯, n}. Then, a_{n}(d), the star content of the graph d, is defined by

a_{n}(d) = _{∑_{b⊆d} ; b∈B[n]}(−1)^{e(d)−e(b)}.  (16)

Proposition 3. |B[n]|_{w_{M}} , the total sum of weights of 2-connected graphs over [n] is given by

|B[n]|_{w_{M}} = ∑_{d∈B[n]} a_{n}(d)w_{RH}(d).  (17)

Proof. Using (14) we can write |B[n]|_{w_{M}} as

|B[n]|_{w_{M}} = ∑_{b∈B[n]} w_{M}(b)

= ∑_{b∈B[n]} ∑_{b⊆d⊆K_{n}}(−1)^{e(d)−e(b)}w_{RH}(d)

= ∑_{d∈B[n]}_{∑_{b⊆d} ; b∈B[n]}(−1)^{e(d)−e(b)}w_{RH}(d)

= ∑_{d∈B[n]} a_{n}(d)w_{RH}(d).

□

So, we can write β_{n} as

β_{n} = \frac{1 − n}{n!} ∑_{b∈B[n]} a_{n}(b)w_{RH}(b).  (18)

Note that since w_{M} and w_{RH} are graph invariants, the sum (17) can be simplified as

|B[n]|_{w_{M}} = ∑_{b̃∈B̃[n]} ℓ(b)w_{M}(b)

= ∑_{b̃∈B̃[n]} ℓ(b)a_{n}(b)w_{RH}(b),  (19)

where B̃[n] is the set of unlabelled graphs b̃ with n vertices and ℓ(b) is the number of labellings of b̃.

For example using the three equations (10)–(12) and (19), the total weight |B[4]|_{w_{M}} may be written as

|B[4]|_{w_{M}} = 1 · w_{M}( ) + 6 · w_{M}( ) + 3 · w_{M}( )
= (−2) · w_{RH}( ) + 0 · w_{RH}( ) + 3 · w_{RH}( )
= 1 · (−2) · w_{RH}( ) + 6 · 0 · w_{RH}( ) + 3 · 1 · w_{RH}( ), (20)

where 1, 6, 3 represent ℓ(b) and (-2), 0, 1 are the star contents a_{4}(b) of the graphs

b =  ,  ,  , respectively.

Proposition 4. We have

∑_{d∈B[n]} a_{n}(d) = 1,  (21)

where B[n] is the set of all 2-connected graphs over [n].

Proof. We have

∑_{d∈B[n]} a_{n}(d) = ∑_{d∈B[n]}_{∑_{b⊆d} ; b∈B[n]}(−1)^{e(d)−e(b)}

= ∑_{b∈B[n]} ∑_{b⊆d⊆K_{n}}(−1)^{e(d)−e(b)}.

Now, for any two graphs b, d ∈ B[n], b ⊆ d ⊆ K_{n} if and only if d\b ⊆ K_{n}\b. Hence, by the binomial theorem

∑_{b⊆d⊆K_{n}}(−1)^{e(d)−e(b)} = ∑_{g⊆K_{n}\b}(−1)^{e(g)}
= (1 + (−1))^{e(K_{n}\b)}

is equal to 1 if b = K_{n} and 0 otherwise. This concludes the proof of (21). □

2.2. Star content of some special graphs. This section is devoted to the study of the star content of some special graphs. We say that a simple graph g over [n] is an extension of another graph h over [n − 1], if g is obtained from h by adding a new vertex n along with some edges between n and the graph h. Let g|_{[n−1]} = g\n denote the restriction of g to the set [n − 1] (that is, the vertex n and all its incident edges are removed).

Proposition 5. Let g a 2-connected graph over [n] such that the vertex n is joined to every other vertex and let g′ = g\n be the graph obtained from g by removing the vertex n and all its incident edges. Then if g′ is also 2-connected, we have

a_{n}(g) = (−1)^{n−1}(n − 2) a_{n−1}(g′).  (22)

In order to prove this proposition, we need first the three following lemmas:

Lemma 6. Let e = {a, b} be an edge of a 2-connected graph G where the vertex a is a cutpoint of the graph G\b. Then, G\e is 2-connected.

Proof. Since G is 2-connected, both a and b are connected to each connected components C_{1}, …, C_{k} of G\a\b (see Figure 1). Moreover, since the vertex a is a cutpoint , the number k of components is at least 2. Consider now a vertex c of G. We have to prove G\c\e is connected. Since G is 2-connected, we know that G\c is connected. Now if c is equal to a or b, the graph G\c\e = G\c is connected. If c ≠ a, b the vertex c belongs to one of the components C_{1}, …, C_{k}, say C_{1}. Moreover a et b are linked by a path of G\c going through C_{2}. Hence e = {a, b} is not an isthmus of G\c and G\c\e is connected. □

Figure 1. A 2-connected graph G with the connected components of G\b\a

Lemma 7. Let h be a 2-connected graph over [n − 1]. Then we have

∑_{g∈B[n]} ; g\n=h(−1)^{e(g)−e(h)} = n − 2·  (23)

Proof. For a 2-connected graph h over the set [n − 1], consider the set

A = {g | g is a graph over [n] and g\n = h},

and define a weight function w over A by

w(g) = (−1)^{e(g)−e(h)}, ∀g ∈ A.

Consider the following involution Inv_{1} acting on the set A:

Inv_{1}(g) = \begin{cases}g\\{1, n\}, & if \{1, n\} ∈ g, \\ g ∪ \{1, n\}, & otherwise. \end{cases}

The total weight of the set A, |A|_{w}, is given by

|A|_{w} = ∑_{g∈A}(−1)^{e(g)−e(h)} = |Fix Inv_{1}|_{w},

where Fix Inv_{1} denotes the set of all fixed points of the involution Inv_{1}. It is easy to see that Inv_{1} has no fixed point. Hence,

|A|_{w} = ∑_{g\n=h}(−1)^{e(g)−e(h)} = 0.  (24)

Moreover, there are n − 1 different ways to obtain an extension g by adding a unique edge between n and h for any 2-connected graph h of size n − 1. In this case, g is not 2-connected. In the same way, there is only one extension g for h by adding the vertex n without new edge and therefore g is also not connected. If we add the vertex n and two or more edges to the graph h, g is always 2-connected. Then we can write (24) as

∑_{g∈B[n]} ; g\n=h(−1)^{e(g)−e(h)} = −_{∑_{g∉B[n]} ; g\n=h}(−1)^{e(g)−e(h)}

= −(−(n − 1) + 1)
= n − 2,

which concludes the proof. □

Lemma 8. Let h be a graph over the set [n − 1] which is not 2-connected. Then we have

∑_{g∈B[n]} ; g\n=h(−1)^{e(g)} = 0·  (25)

Proof. For a graph h over the set [n − 1] which is not 2-connected, consider the set

B = {g | g is a 2−connected graph over [n] and g\n = h}.

If h is not connected then B = ∅ and (25) is trivially satisfied. If h is connected let a be the cutpoint of h having the smallest label. Define the following weight function w over B :

w(g) = (−1)^{e(g)}, ∀g ∈ B.

Consider the following involution Inv_{2} acting on the set B :

Inv_{2}(g) = \begin{cases}g\\{a, n\}, & if \{a, n\} ∈ g, \\ g ∪ \{a, n\}, & otherwise. \end{cases}

Note that for all g ∈ B, Inv_{2}(g) is 2-connected by Lemma 6. Hence, B is stable by the involution Inv_{2}. We deduce that

|B|_{w} = ∑_{g∈B}(−1)^{e(g)} = |Fix Inv_{2}|_{w},

where Fix Inv_{2} denotes the set of all fixed points of the involution Inv_{2}. Again, the involution Inv_{2} has no fixed point. Hence,

|B|_{w} = ∑_{g\n=h}(−1)^{e(g)} = 0·

□

We are now able to prove Proposition 5.

Proof of Proposition 5. Let g a be 2-connected graph over [n] such that the vertex n is joined to every other vertex and let g′ = g\n. From (16) we have successively

a_{n}(g) = _{∑_{h⊆g} ; h∈B[n]}(−1)^{e(h)−e(g)}

= _{∑_{h⊆g} ; h∈B[n];h\n∈B[n−1]}(−1)^{e(h)−e(g)} +_{∑_{h⊆g} ; h∈B[n];h\n∉B[n−1]}(−1)^{e(h)−e(g)}

= _{∑_{h′⊆g′} ; h′∈B[n−1]}(−1)^{e(g)−e(h′)} _{∑_{h∈B[n]} ; h\n=h′}(−1)^{e(h)−e(h′)}

+_{∑_{h′⊆g′} ; h′∉B[n−1]}(−1)^{e(g)} _{∑_{h∈B[n]} ; h\n=h′}(−1)^{e(h)}

= (−1)^{n−1}_{∑_{h′⊆g′} ; h∈B[n−1]}(−1)^{e(g′)−e(h′)}(n − 2) + 0 (by Lemmas 7 and 8)

= (−1)^{n−1}(n − 2)a_{n−1}(g′)·

□

Corollary 9. Let n > m and let g be a 2-connected graph over [n] such that for i = 0, …, n − m − 1, vertex n − i is joined to every vertex j < n − i, and let g^{(n−m)} = g\n\n − 1\ ⋯ \m + 1 be the graph obtained from g by removing the vertices n, n − 1, …, m + 1 and all their incident edges. Then if g^{(n−m)} is also 2-connected,

a_{n}(g) = (−1)^{\binom{n}{2}−\binom{m}{2}} \frac{(n − 2)!}{(m − 2)!} a_{m}(g^{(n−m)}).  (26)

Remark 2. In particular, taking g = K_{n} and m = 2 in (26) we have, for n > 2,

a_{n}(K_{n}) = (−1)^{\binom{n}{2}+1}(n − 2)!  (27)

3. Hard-core continuum gas in one dimension

Consider n hard particles of diameter 1 on a line segment. The hard-core constraint translates into the interaction potential φ, with φ(r) = ∞, if r < 1, and φ(r) = 0, if r ≥ 1, and the Mayer function f and the Ree–Hoover function \overline{f} are given by (7). Hence, we can write the Mayer weight function w_{M}(c) of a connected graph c as

w_{M}(c) = (−1)^{e(c)} ∫_{ℝ^{n−1}} ∏_{{i,j}∈c} χ(|x_{i} − x_{j}| < 1)dx_{1} … dx_{n−1}, x_{n} = 0, (28)

and the Ree–Hoover weight function w_{RH}(c) of a 2-connected graph c as

w_{RH}(c) = (−1)^{e(c)} ∫_{ℝ^{n−1}} ∏_{{i,j}∈c} χ(|x_{i} − x_{j}| < 1) ∏_{{i,j}∉c} χ(|x_{i} − x_{j}| > 1)dx_{1} … dx_{n−1},

(29)

with x_{n} = 0 and where e(c) is the number of edges of c. Note that w_{M}(c) = (−1)^{e(c)}Vol(P(c)), where P(c) is the polytope defined by

P(c) = {X ∈ ℝ^{n} | x_{n} = 0, |x_{i} − x_{j}| < 1 ∀{i, j} ∈ c} ⊆ ℝ^{n−1} × {0} ⊆ ℝ^{n},

where X = (x_{1}, …, x_{n}). Similarly, w_{RH}(c) = (−1)^{e(c)}Vol(P_{RH}(c)), where P_{RH}(c) is the union of polytopes defined by

P_{RH}(c) = {X ∈ ℝ^{n} | x_{n} = 0, |x_{i} − x_{j}| < 1 ∀{i, j} ∈ c,

|x_{i} − x_{j}| > 1 ∀\{i, j\} ∈ \overline{c}\} ⊆ ℝ^{n−1} × \{0\} ⊆ ℝ^{n}.

3.1. Why many graphs have Ree–Hoover weight equal to 0. When the Ree–Hoover transformation is made, many graphs have zero star content and hence do not contribute to the virial coefficient. In addition, some Ree–Hoover graph weights may be zero for geometrical reasons. We found sufficient conditions for families of graphs which guaranty the nullity of their Ree–Hoover weights. We introduce first some variants of the notion of subgraph and an associated lemma:

Definition 10. Let g be a simple graph on the vertex set U and g′ be a subgraph of g on the vertex set U′ ⊆ U. The graph g′ is said to be induced by g if

g′ = g ∩ K_{U′},  (30)

where K_{U′} is the complete graph on U′. If a graph h is isomorphic to an induced subgraph of g, we write h \overline{⊆} g.

Proposition 11. Let g and h be two 2-connected graphs. In the case of hard-core continuum gas in one dimension, we have:

h \overline{⊆} g and w_{RH}(h) = 0 implies w_{RH}(g) = 0.  (31)

Proof. Without loss of generality, we can suppose that h is a subgraph of g where the vertex set of h is [m] and the one of g is [n]. By hypothesis, w_{RH}(h) = 0, that is, the system S_{h} of inequalities

|x_{i} − x_{j}| < 1 for {i, j} ∈ h
and |x_{i} − x_{j}| > 1 for {i, j} ∈ K_{m}\h

is contradictory. Consider now the system S_{g},

|x_{i} − x_{j}| < 1 for {i, j} ∈ g
and |x_{i} − x_{j}| > 1 for {i, j} ∈ K_{m}\g.

The system S_{g} has more “<” constraints and more “>” constraints than S_{h}. Thus, S_{g} must be also contradictory. That is w_{RH}(g) = 0. □

3.2. Sufficient conditions for w_{RH} = 0.

Theorem 12. The Ree–Hoover weight of a 2-connected graph g of size n is zero if g satisfies one of the following conditions,

g is not chordal : ∃ k ≥ 4, C_{k} \overline{⊆} g,  (32)
or g has a claw : S_{3} \overline{⊆} g,  (33)

where S_{3} is the 3-star graph (see Figure 4).

Proof. • In order to prove (32) it is sufficient, by Proposition 11, to show that w_{RH}(C_{k}) = 0, for k ≥ 4, where C_{k} is the standard cycle graph {{1, 2}, {2, 3}, …, {k − 1, k}, {1, k}}. Therefore, the associated system of inequalities is contradictory. Without loss of generality, we can assume that x_{1} ≤ x_{2}. Then x_{2} < x_{3} since |x_{1} − x_{2}| ≤ 1, |x_{2} − x_{3}| ≤ 1 and |x_{1} − x_{3}| ≥ 1. For the same reason x_{i} < x_{i+1} for all i = 1, …, k, with the convention that x_{k+1} = x_{1}. So we obtain x_{1} ≤ x_{2} < x_{3} < … < x_{k} < x_{1} which is a contradiction.

• In order to prove (33) it is sufficient, by Proposition 11, to show that w_{RH}(S_{3}) = 0 where S_{3} = {{1, 4}, {2, 4}, {3, 4}}. Without loss of generality, we can assume that x_{4} = 0, x_{1} ≤ x_{2} ≤ x_{3}. Since |x_{i}| = |x_{i} − x_{4}| < 1, for i = 1, 3, we have |x_{3}−x_{1}| < 2. This is incompatible with the conditions |x_{1} − x_{2}| > 1, |x_{2} − x_{3}| > 1, since |x_{3} − x_{1}| = (x_{3} − x_{2}) + (x_{2} − x_{1}) > 2.

□

3.3. The method of graph homomorphisms adapted to the Ree–Hoover weight. The method of graph homomorphisms was introduced by Labelle, Leroux and Ducharme [7] for the exact computation of the Mayer weight w_{M}(b) of an arbitrary 2-connected graph b in the context of hard-core continuum gases in one dimension. Since w_{M}(b) = (−1)^{e(b)}Vol(P(b)), the computation of w_{M}(b) is reduced to the computation of the volume of the polytope P(b) associated to b. In order to evaluate this volume, the polytope P(b) is decomposed into ν(b) simplices which are all of volume 1/(n − 1)!. This yields Vol(P(b)) = ν(b)/(n − 1)!. The simplices are encoded by a diagram associated to the integral parts and the relative positions of the fractional parts of the coordinates x_{1}, …, x_{n} of points X ∈ P(b).

More precisely, to each real number x, they associate an ordered pair (ξ_{x}, h_{x}), called the fractional representation of x, where h_{x} = ⌊x⌋ is the integral part of x and ξ_{x} = x − h_{x} is the (positive) fractional part of x, so that x = ξ_{x} + h_{x}. Then, for x ≠ y, the condition |x−y| < 1 translates into “assuming ξ_{x} < ξ_{y}, then h_{x} = h_{y} or h_{x} = h_{y} + 1”. Geometrically, the slope of the line segment between the points (ξ_{x}, h_{x}) and (ξ_{y}, h_{y}) in the plane should be either null or negative. Now consider a 2-connected graph b with vertex set V = [n] = {1, 2, …, n}, and let X = (x_{1}, …, x_{n}) be a point in the polytope P(b). Let us write (ξ_{i}, h_{i}) for the fractional representation of the coordinate x_{i} of X, i = 1, …, n. For x_{n} = 0, it will be convenient to use the special representation ξ_{n} = 1.0 and h_{n} = −1. The volume of P(b) is not changed by removing all hyperplanes {x_{i} − x_{j} = k}, for k ∈ ℤ. Hence, we can assume that all the fractional parts ξ_{i} are distinct. We form a subpolytope of P(b) by keeping the “heights” h_{1}, h_{2}, …, h_{n} fixed as well as the relative positions (total order) of the fractional parts ξ_{1}, ξ_{2}, …, ξ_{n}. Let h : V → ℤ denote the height function i ↦ h_{i} and β : V → [n] be the permutation of [n] for which β(i) gives the rank of ξ_{i} in this total order. Note that β(n) = n. The corresponding simplex will be denoted by P(h, β). Explicitly, each simplex can be written as

P(h, β) = {(h_{1} + ξ_{1}, …, h_{n−1} + ξ_{n−1}, 0) | 0 < ξ_{β^{−1}(1)} < ⋯ < ξ_{β^{−1}(n−1)} < 1} (34)

and it is shown in [7] (see also [5] for more details) that each such simplex is affine-equivalent (with jacobian 1) to the standard simplex

P(0, id) = {(ξ_{1}, ξ_{2}, …, ξ_{n−1}, 0) | 0 < ξ_{1} < ξ_{2} < ⋯ < ξ_{n−1} < 1}

in ℝ^{n−1} × {0}, of volume 1/(n − 1)!.

Note that the simplices (34) are disjoint and each such simplex can be characterized by its centre of gravity

X_{h,β} = (h_{1} + \frac{β(1)}{n}, h_{2} + \frac{β(2)}{n}, …, h_{n−1} + \frac{β(n − 1)}{n}, 0) ∈ ℝ^{n−1} × \{0\}.

Note also that when there are no restrictions on h and β, the union of the closed simplices \overline{P(h, β)} coincides with the whole configurations space ℝ^{n−1} × \{0\}.

Using the fractional coordinates to represent the center of gravity X_{h,β} of the simplex P(h, β), and drawing a line segment form x_{i} = (h_{i}, ξ_{i}) and x_{j} = (h_{j}, ξ_{j}) for each edge {i, j} of the graph b, we obtain a configuration in the plane which can be seen as an homomorphic image of b and which characterizes the subpolytope P(h, β). For example, take n = 6 and

b = {{1, 3}, {1, 5}, {1, 6}, {2, 3}, {2, 4}, {5, 6}}.

Figure 2 illustrates the corresponding configuration, where the homomorphic image of b appears clearly. The next proposition summarizes the above discussion.

Proposition 13. ([7]). Let b be a 2-connected graph with vertex set V = [n] and consider a function h : V → ℤ and a bijection β : V → [n] satisfying β(n) = n. Then the simplex P(h, β) corresponding to the pair (h, β) is contained in the polytope P(β) if and only if the following condition is satisfied:

for any edge {i, j} of b, β(i) < β(j) implies h_{i} = h_{j} or h_{i} = h_{j} + 1. (35)

3210 −1  x_{5}  x_{6} x_{4}  x_{2}  x_{3} x_{1} ξ^{4} < ξ^{1} < ξ^{2} < ξ^{5} < ξ^{3} < ξ^{6} 3 2  4 5 6  h_{1} = 0 1  h_{5} = −1 h_{2} = 1 h_{3} = 0 h_{4} = 2 h_{6} = −1

Figure 2. Fractional representation of a simplicial subpolytope of a graph b

Corollary 14. ([7]). Let b be a 2-connected graph and let ν(b) be the number of pairs (h, β) such that the condition (35) is satisfied. Then the volume of the polytope P(b) is given by

Vol(P(b)) = ν(b)/(n − 1)!.  (36)

Proposition 14 can be used to compute the weight of some families of graphs, since w_{M}(b) = (−1)^{e(b)}Vol(P(b)).

In a similar way we can adapt the above configurations to the context of the Ree–Hoover weight.

Proposition 15. Let b be a 2-connected graph with vertex set V = [n] and consider a function h : V → ℤ and a bijection β : V → [n] satisfying β(n) = n. Then the simplex P(h, β) corresponding to the pair (h, β) is contained in the polytope P_{RH}(b) if and only if the following conditions are satisfied:

for any edge {i, j} of b, β(i) < β(j) implies h_{i} = h_{j} or h_{i} = h_{j} + 1,  (37)
for any edge \{i, j\} of \overline{b}, β(i) < β(j) implies h_{i} ≤ h_{j} − 1 or h_{i} ≥ h_{j} + 2. (38)

Proof. Condition (37) expresses exactly that |x_{i} − x_{j}| < 1, whenever {i, j} is an edge of b, and condition (38) expresses exactly that |x_{i} − x_{j}| > 1, whenever {i, j} is an edge of \overline{b}, that is, the defining conditions for the domain of integration of (29). □

Proposition 16. Let b be a 2-connected graph and let ν_{RH}(b) be the number of pairs (h, β) such that conditions (37) and (38) are satisfied. Then the volume of P_{RH}(b) is given by

Vol(P_{RH}(b)) = ν_{RH}(b)/(n − 1)!.  (39)

Proof. It is clear that the polytope P_{RH}(b) is the disjoint union of all its subpolytopes P(h, β) and the result follows immediately. □

Proposition 16 can be used to compute the weight of some families of graphs, since w_{RH}(b) = (−1)^{e(b)}Vol(P_{RH}(b)).

4. Ree–Hoover weight of some infinite families of graphs

Here are some of our results concerning explicit formulas for the Ree–Hoover weight of certain infinite families of graphs. These were first conjectured from numerical values using Ehrhart polynomials. Their proofs use the techniques of graph homorphisms. The weights of 2-connected graphs b are given in absolute value |w(b)|, the sign being always equal to (−1)^{e(b)}.

Lemma 17. Suppose that g is a graph over [n] and i, j ∈ [n − 1] are such that g does not contain the edge {n, i} but contains the edges {i, j} and {n, j}. In this case, any RH-configuration (h, β) (with h_{n} = −1, β(n) = n) satisfies either one of the following conditions:

(1) h_{i} = 1, h_{j} = 0 and β(i) < β(j),

(2) h_{i} = −2, h_{j} = −1 and β(i) > β(j).

4.1. The Ree–Hoover weight of the graph K_{n}\S_{k}. Let S_{k} denote the k-star graph with vertex set [k + 1] and edge set {{1, 2}, {1, 3}, …, {1, k + 1}}. As a first example, we compute |w_{RH}(K_{n}\e)|, with K_{n}\e = K_{n}\S_{1}.

Proposition 18. For n ≥ 3, let K_{n}\e denote the complete graph on n vertices from which an arbitrary edge has been removed. Then we have

|w_{RH}(K_{n}\e)| = \frac{2}{(n − 1)}·  (40)

Proof. We can assume that the missing edge is e = {1, n}. According to Lemma 17 with 1, …, k, j = k + 1, …, n − 1, there are two possibilities for h: a) set h_{1} = 1, h_{n} = −1 and all other h_{i} = 0, so that β(1) must be 1, and b) set h_{1} = −2 and all other h_{i} = −1, so that β(1) must be n − 1. In both cases β can be extended in (n − 2)! ways, giving the possible relative positions of the x_{i}, 2 ≤ i ≤ n − 1 (see Figure 3). So, there are 2(n − 2)! RH-configurations (h, β).

x_{1} x_{1}  x_{n}  x_{n} x_{i}  x_{i}^{1}  ^{1}

Figure 3. Fractional representation of a simplicial subpolytope of P_{RH}(K_{n}\e)

□

Note that, from (15) and the known fact that |w_{M}(K_{n})| = n, we have

w_{M}(K_{n}\e) = (−1)^{\binom{n}{2}−1} (n + \frac{2}{(n − 1)}) ,  (41)

since

|w_{M}(K_{n}\e)| = |w_{RH}(K_{n})| + |w_{RH}(K_{n}\e)|.

In the general case we have:

Proposition 19. For k ≥ 1, n ≥ k + 3, we have

|w_{RH}(K_{n}\S_{k})| = \frac{2k!}{(n − 1)(n − 2) ⋯ (n − k)}·  (42)

Proof. We assume that the missing edges are {1, n}, {2, n}, …, {k, n} (see Figure 4, for the case of S_{3}).

3  1 n 2

Figure 4. The graph S_{3}

According to Lemma 17 with 1, …, k, j = k + 1, …, n − 1, there are two possibilities for h:

• h_{1} = h_{2} = ⋯ = h_{k} = 1 and h_{n} = −1 and all other h_{i} = 0, so that

(β(1), β(2), …, β(k)) must be a permutation of {1, 2, …, k},

• h_{1} = h_{2} = ⋯ = h_{k} = −2 and all other h_{i} = −1, so that (β(1), β(2), …,

β(k)) must be a permutation of {n − 1, n − 2, …, n − k}.

In each case β can be extended in (n − (k + 1))! ways, giving the possible relative positions of the x_{i}, k + 1 ≤ i ≤ n − 1 (see Figure 5, for the case of S_{3}). So, there are 2k!(n − k − 1)! RH-configurations (h, β).

x_{3}  x_{n}  x_{2} x_{1} x_{2}  x_{n} x_{1} x_{3} x_{i}  x_{i}^{1}  ^{1}

Figure 5. Fractional representation of a simplicial subpolytope of P_{RH}(K_{n}\S_{3})

□

4.2. The Ree–Hoover weight of the graph K_{n}\(S_{j}–S_{k}). Let S_{j}–S_{k} denote the graph obtained by joining with a new edge the centers of a j-star and of a k-star. See Figure 6 for an example.

Figure 6. The graph S_{3}–S_{4}

Let us start with the simple case S_{1}–S_{1}.

Proposition 20. For n ≥ 5, we have

|w_{RH}(K_{n}\S_{1}−S_{1})| = \frac{2}{(n − 1)(n − 2)(n − 3)}·  (43)

Proof. We can assume that the missing edges are {1, n}, {2, n} and {2, 3} (see Figure 7). According to Lemma 17 with i = 1, …, k + 1 and j = k + 2, …, n − 1 for i ≠ 2 and j = k + j + 2, …, n − 1 for i = 2, there are two possibilities for h:

• h_{1} = h_{2} = 1 and h_{n} = −1 and all other h_{i} = 0, so that (β(1), β(2), β(3))

must be (1, 3, 2),

• h_{1} = h_{2} = −2 and all other h_{i} = −1, so that (β(1), β(2), β(3)) must be

(n − 1, n − 3, n − 2).

In each case β can be extended in (n − 4)! ways, giving the possible relative positions of the x_{i}, 4 ≤ i ≤ n − 1 (see Figure 8). So, there are 2(n − 4)! RHconfigurations (h, β).

1  n 2 3
Figure 7. The graph S_{1}–S_{1}

x_{2}  x_{n} x_{1}  x_{n} x_{1} x_{2} x_{i}  x_{i} x_{3}  x_{3}^{1}  ^{1}

Figure 8. Fractional representation of a simplicial subpolytope of P_{RH}(K_{n}\S_{1}–S_{1})

□

In the general case we have:

Proposition 21. For j ≥ k ≥ 1, n ≥ k + j + 3, we have

|w_{RH}(K_{n}\(S_{j}−S_{k}))| = \frac{2k!j!}{(n − 1)(n − 2) ⋯ (n − (k + j + 1))}·  (44)

Proof. We can assume that the missing edges are {1, n}, {2, n}, …, {k + 1, n} and {2, k + 2}, {2, k + 3}, …,{2, k + j + 1} (see Figure 9, for the case of S_{2}–S_{3}). According to Lemma 17 there are two possibilities for h:

6  2 5  4 1  3 n
Figure 9. The graph S_{2}–S_{3}

• h_{1} = h_{2} = ⋯ = h_{k+1} = 1 and h_{n} = −1 and all other h_{i} = 0, so that (β(1), β(3), …, β(k + 1)) must be a permutation of {1, 2, …, k} and (β(k + 2), β(k + 3), …, β(k + j + 1)) must be a permutation of

{k + 1, …, k + j} and β(2) = k + j + 1.

• h_{1} = h_{2} = ⋯ = h_{k+1} = −2 and all other h_{i} = −1, so that (β(1), β(3), …, β(k + 1)) must be a permutation of {n − 1, n − 2, …, n − k} and (β(k + 2), β(k + 3), …, β(k + j + 1)) must be a permutation of

{n − k − 1, …, n − k − j} and β(2) = n − k − j − 1.

In each case β can be extended in (n − (k + j + 2))! ways, giving the possible relative positions of the x_{i}, k + j + 2 ≤ i ≤ n − 1 (see Figure 10, for the case of S_{2}–S_{3}). So, there are 2k!j!(n − (k + j + 2))! RH-configurations (h, β).

x_{4} x_{5}  x_{3} x_{1} x_{n}  x_{n} x_{1}  x_{i} x_{i} x_{2} x_{3} x_{4}x_{6} x_{5}  x_{2} x_{6}^{1}  ^{1}

Figure 10. Fractional representation of a simplicial subpolytope of P_{RH}(K_{n}\S_{2}–S_{3})

□

4.3. The Ree–Hoover weight of the graph K_{n}\(C_{4} · S_{k}). Let C_{4} · S_{k} denote the graph obtained by identifying one vertex of the graph C_{4} with the center of a k-star. See Figure 11 for an example.

Figure 11. The graph C_{4} · S_{4}

Let us start with the special case k = 0 corresponding to the graph K_{n}\C_{4}. The proof is diffferent from the one corresponding to the case k ≥ 1.

4.3.1. The Ree–Hoover weight of the graph K_{n}\C_{4}.

Proposition 22. For n ≥ 6, we have

|w_{RH}(K_{n}\C_{4})| = \frac{8}{(n − 1)(n − 2)(n − 3)},  (45)

where C_{4} is the unoriented cycle with 4 vertices.

Proof. We can assume that the missing edges are {1, n}, {2, n}, {2, 3} and {3, 1} (see Figure 12). There are four possibilities for h:

• h_{1} = h_{2} = 1 and h_{n} = −1 and all other h_{i} = 0, so that (β(1), β(2)) must be a permutation of {2, 3} and β(3) = 1,

• h_{1} = h_{2} = 1 and h_{n} = h_{3} = −1 and all other h_{i} = 0, so that (β(1), β(2)) must be a permutation of {1, 2} and β(3) = n − 1,

• h_{1} = h_{2} = −2 and all other h_{i} = −1, so that (β(1), β(2)) must be a permutation of (n − 2, n − 3) and β(3) = n − 1,

• h_{1} = h_{2} = −2, h_{3} = 0 and all other h_{i} = −1, so that (β(1), β(2)) must be a permutation of (n − 1, n − 2) and β(3) = 1.

In each case β can be extended in (n − 4)! ways, giving the possible relative positions of the x_{i}, 4 ≤ i ≤ n − 1 (see Figure 13). So, there are 4 · 2!(n − 4)! RH-configurations (h, β).

13  2n

Figure 12. The graph C_{4}

x_{n}  x_{n} x_{n}  x_{n} x_{2} x_{3} x_{3}  x_{2} x_{3} x_{1} x_{2} x_{1}  x_{i} x_{i} x_{2}  x_{3} x_{i}  x_{1} x_{1}x_{i}  ^{1}^{1}  ^{1}^{1}

Figure 13. Fractional representation of a simplicial subpolytope of P_{RH}(K_{n}\C_{4})

□

Proposition 23. For k ≥ 1, n ≥ k + 5, we have

|w_{RH}(K_{n}\(C_{4} · S_{k}))| = \frac{4k!}{(n − 1)(n − 2) ⋯ (n − (k + 3))}.  (46)

Proof. We can assume that the missing edges are {1, n}, {2, n}, {4, n}, …, {k + 3, n} and {1, 3}, {2, 3} (see Figure 14, for the case of C_{4} · S_{2}).

1  45 2 3  n
Figure 14. The graph C_{4} · S_{2}

According to Lemma 17 there are two possibilities for h:

• h_{1} = h_{2} = h_{4} ⋯ = h_{k+3} = 1 and h_{n} = −1 and all other h_{i} = 0, so that (β(4), β(5), …, β(k + 3)) must be a permutation of {1, 2, …, k} and (β(1), β(2)) must be a permutation of {k + 2, k + 3} and β(3) = k + 1,

• h_{1} = h_{2} = h_{4} ⋯ = h_{k+3} = −2 and all other h_{i} = −1, so that (β(4), β(5), …, β(k + 3)) must be a permutation of {n − 1, n − 2, …, n − k} and (β(1), β(2)) must be a permutation of {n − k − 2, n − k − 3} and β(3) = n − k − 1.

In each case β can be extended in (n − (k + 4))! ways, giving the possible relative positions of the x_{i}, k + 4 ≤ i ≤ n − 1 (see Figure 15, for the case of C_{4} · S_{2}). So, there are 2 · 2! k! (n − (k + 4))! RH-configurations (h, β).

x_{n} x_{5} x_{1}  x_{4} x_{n}  x_{i} x_{3}  x_{3} x_{i} x_{5} x_{4}  x_{2} x_{1}  x_{2}^{1}  ^{1}

Figure 15. Fractional representation of a simplicial subpolytope of P_{RH}(K_{n}\(C_{4} · S_{2}))

□

Note that the formula (45) is not a special case of (46).

4.4. The Ree–Hoover weight of the graph K_{n}\P_{k}. Let P_{k} denote the path graph with vertex set [k] and edge set {{1, 2}, {2, 3}, …, {k−1, k}}. For n ≥ 5, we have K_{n}\P_{3} = K_{n}\S_{2} and K_{n}\P_{4} = K_{n}\S_{1}–S_{1}. Thus, the weights w_{RH}(K_{n}\P_{3}) and w_{RH}(K_{n}\P_{4}) can be obtained as special cases of Propositions 19 and 20. Moreover, w_{RH}(K_{n}\P_{k}) = 0, for k ≥ 5, n ≥ k + 1, which is a consequence of Theorem 12. Indeed, C_{4} \overline{⊆} K_{n}\P_{k} and we conclude using (32).

5. Mayer weight of some infinite families of graphs

In this section, we give explicit formulas for the Mayer weight of the above infinite families of graphs. In order to do so, we use the following formula

|w_{M}(b)| = ∑_{b⊆d⊆K_{n}} |w_{RH}(d)|  (47)

which is a consequence of (14) since |w_{M}(b)| = (−1)^{e(b)}w_{M}(b) and |w_{RH}(d)| = (−1)^{e(d)}w_{RH}(d) in the case of hard-core continuum gases in one dimension. Substituting K_{n}\g and K_{n}\k for b and d in (47), we have

|w_{M}(K_{n}\g)| = ∑_{k⊆g} |w_{RH}(K_{n}\k)|
= ∑_{h̃⊆g̃} m(h̃, g̃)|w_{RH}(K_{n}\h)|,  (48)

where g̃ denotes the unlabelled graph corresponding to g, h̃ runs through the unlabelled subgraphs of g̃ and m(h̃, g̃) is the number of ways of obtaining h̃ by removing some edges in h̃. In the following propositions these multiplicities m(h̃, g̃) are obtainable in each case by direct combinatorial arguments.

5.1. The Mayer weight of the graph K_{n}\S_{k}.

Proposition 24. For k ≥ 1, n ≥ k + 3, we have

|w_{M}(K_{n}\S_{k})| = n + 2 ∑_{j=1}^{k} \frac{j!\binom{k}{j}}{(n − 1)(n − 2) ⋯ (n − j)}.

Proof. The over graphs of K_{n}\S_{k} are up to isomorphism of the form: K_{n}\S_{j}, 1 ≤ j ≤ k and K_{n}. Their multiplicities m(S_{j}, S_{k}) are given by m(S_{j}, S_{k}) = \binom{k}{j} because one has to choose j edges among the k edges incident to the center of the star. Note that S_{0} = ∅ is the star with no edge. Hence,

|w_{M}(K_{n}\S_{k})| = ∑_{j=0}^{k} \binom{k}{j}|w_{RH}(K_{n}\S_{j})|.

We conclude using Proposition 19. □

5.2. The Mayer weight of the graph K_{n}\S_{j}–S_{k}.

Proposition 25. For j ≥ k ≥ 1, n ≥ k+j+3, we have, with the usual convention \binom{k+1}{ℓ} = 0 if ℓ > k + 1,

|w_{M}(K_{n}\(S_{j}−S_{k}))| = n + ∑_{l=1}^{j+1} 2 [\binom{j + 1}{l} + \binom{k + 1}{l}] \frac{l!}{(n − 1) ⋯ (n − l)}

+ ∑_{m=1}^{j} ∑_{l=1}^{k} 2\binom{j}{m}\binom{k}{l}\frac{m!l!}{(n − 1) ⋯ (n − (m + l + 1))} − \frac{2}{(n − 1)}.

Proof. The over graphs of K_{n}\S_{j}–S_{k} whose Ree–Hoover weight is not zero are up to isomorphism of the form: K_{n}\S_{l}, 1 ≤ l ≤ j + 1, K_{n}\(S_{m}–S_{l}), 1 ≤ m ≤ j, 1 ≤ l ≤ k and K_{n}. Their multiplicities are given by

m(S_{l}, S_{j}−S_{k}) = \binom{j+1}{l} + \binom{k+1}{l}, l ≥ 2, m(S_{1}, S_{j}−S_{k}) = \binom{j+1}{l} + \binom{k+1}{l} − 1,

m(S_{m}−S_{l}, S_{j}−S_{k}) = \binom{j}{m}\binom{k}{l}.

Hence,

|w_{M}(K_{n}\(S_{j}−S_{k}))| = |w_{RH}(K_{n})| + ∑_{l=1}^{j+1} [\binom{j + 1}{l} + \binom{k + 1}{l}] |w_{RH}(K_{n}\S_{l})|

+ ∑_{m=1}^{j} ∑_{l=1}^{k} \binom{j}{m}\binom{k}{l}|w_{RH}(K_{n}\(S_{m}−S_{l}))| − |w_{RH}(K_{n}\S_{1})|.

We conclude using Propositions 19 and 21. □ 5.3. The Mayer weight of the graph K_{n}\C_{4}. Proposition 26. For n ≥ 6, we have

|w_{M}(K_{n}\C_{4})| = n + \frac{8}{(n − 1)} + \frac{16}{(n − 1)(n − 2)} + \frac{16}{(n − 1)(n − 2)(n − 3)}.

Proof. Note first that the RH-weight of the over graph K_{n}\S_{1}\S_{1} of K_{n}\C_{4} is 0. The other over graphs of K_{n}\C_{4} are, up to isomorphism, of the form: K_{n}\S_{1}, K_{n}\S_{2}, K_{n}\C_{4}, K_{n}\(S_{1} − S_{1}) and K_{n}. Their multiplicities are given by

m(S_{l}, C_{4}) = 4, 1 ≤ l ≤ 2, m(S_{1}−S_{1}, C_{4}) = 4.

Hence,

|w_{M}(K_{n}\C_{4})| = |w_{RH}(K_{n})| + ∑_{l=1}^{2} 4|w_{RH}(K_{n}\S_{l})|

+ 4|w_{RH}(K_{n}\(S_{1} − S_{1}))| + |w_{RH}(K_{n}\C_{4})|.

We conclude using Propositions 19, 20 and 22. □ 5.4. The Mayer weight of the graph K_{n}\(C_{4} · S_{k}). Proposition 27. For k ≥ 1, n ≥ k + 5, we have

|w_{M}(K_{n}\(C_{4} · S_{k}))| = n + ∑_{l=1}^{k+2} 2\binom{k + 2}{l}\frac{l!}{(n − 1) ⋯ (n − l)}

+ ∑_{l=1}^{k} 4\binom{k}{l}\frac{l!}{(n − 1) ⋯ (n − (l + 3))}

+ ∑_{l=1}^{k+1} 4 [\binom{k}{l − 1} + \binom{k}{l}] \frac{l!}{(n − 1) ⋯ (n − (l + 2))}

+ \frac{4}{n − 1} + \frac{12}{(n − 1) (n − 2)} + \frac{16}{(n − 1) (n − 2) (n − 3)}.

Proof. The over graphs of K_{n}\(C_{4} · S_{k}) whose Ree–Hoover weight is not zero are up to isomorphism of the form: K_{n}\S_{l}, 1 ≤ l ≤ k + 2, K_{n}\(C_{4} · S_{l}), 1 ≤ l ≤ k, K_{n}\(S_{1}–S_{l}), 1 ≤ l ≤ k + 1, C_{4} and K_{n}. Their multiplicities are given by

m(S_{l}, C_{4} · S_{k}) = \binom{k+2}{l}, l ≥ 3, m(S_{1}, C_{4} · S_{k}) = \binom{k+2}{l} + 2,

m(S_{2}, C_{4} · S_{k}) = \binom{k+2}{l} + 3, m(C_{4} · S_{l}, C_{4} · S_{k}) = \binom{k}{l},

m(S_{1}−S_{l}, C_{4} · S_{k}) = 2 [\binom{k}{l−1} + \binom{k}{l}] , l ≥ 2, m(S_{1}−S_{1}, C_{4} · S_{k}) = 2\binom{k}{1} + 4.

Hence,

|w_{M}(C_{4} · S_{k})| = |w_{RH}(K_{n})| + ∑_{l=1}^{k+2} \binom{k + 2}{l}|w_{RH}(K_{n}\S_{l})|

+ ∑_{l=1}^{k} \binom{k}{l}|w_{RH}(K_{n}\C_{4} · S_{l})| + 2|w_{RH}(K_{n}\S_{1})|

+ ∑_{l=1}^{k+1} 2 [\binom{k}{l − 1} + \binom{k}{l}] |w_{RH}(K_{n}\(S_{1} − S_{l}))|

+ 3|w_{RH}(K_{n}\S_{2})| + |w_{RH}(K_{n}\C_{4})| + 4|w_{RH}(K_{n}\S_{1} − S_{1})|.

We conclude using Propositions 19–23. □

5.5. The Mayer weight of the graph K_{n}\P_{k}.

Proposition 28. For k ≥ 5, n ≥ k + 1, we have

|w_{M}(K_{n}\P_{k})| = n + \frac{2(k − 1)}{(n − 1)} + \frac{4(k − 2)}{(n − 1)(n − 2)} + \frac{2(k − 3)}{(n − 1)(n − 2)(n − 3)}.

Proof. The over graphs of K_{n}\P_{k}, k ≥ 5, whose Ree–Hoover weight is not zero are up to isomorphism of the form: K_{n}\S_{1}, K_{n}\S_{2}, K_{n}\P_{4} and K_{n}. Their multiplicities are given by

m(S_{l}, P_{k}) = k − l, 1 ≤ l ≤ 2, m(P_{4}, P_{k}) = k − 3.

Hence,

|w_{M}(K_{n}\P_{k})| = |w_{RH}(K_{n})| + (k − 1)|w_{RH}(K_{n}\S_{1})| + (k − 2)|w_{RH}(K_{n}\S_{2})| + (k − 3)|w_{RH}(K_{n}\P_{4})|.

We conclude using Propositions 19 and 20. □

References

[1] O. Bernardi, “Solution to a combinatorial puzzle arising from Mayer’s theory of cluster integrals.” Séminaire Lotharingien de Combinatoire 59 (2008), Article B59e.

[2] N. Clisby and B. M. McCoy, “Negative virial coefficients and the dominance of loose packed diagrams for D-dimensional hard spheres.” Journal of Statistical Physics 114 (2004), 1361–1392.

[3] N. Clisby and B. M. McCoy, “Ninth and tenth order virial coefficients for hard spheres in D dimensions.” Journal of Statistical Physics 122 (2006), 15–57.

[4] N. Clisby, Negative Virial Coefficients for Hard Spheres. PhD thesis, Stony Brook University, Stony Brook, New York, May (2004).

[5] A. Kaouche, Invariants de graphes liés aux gaz imparfaits. PhD thesis, Université du Québec à Montréal, 2009.

[6] A. Kaouche and P. Leroux, “Tables for the Mayer and Ree– Hoover graph weights of 2-connected graphs of size 4 to 7.”

[http://www.lacim.uqam.ca/∼kaouche/TableauRH7.pdf] “Tables for the

Mayer and Ree–Hoover graph weights of 2-connected graphs of size 8.”

[http://www.lacim.uqam.ca/∼kaouche/TableauRH8.pdf] (2007).

[7] G. Labelle, P. Leroux and M. G. Ducharme, “Graph weights arising from Mayer’s theory of cluster integrals.” Séminaire Lotharingien de Combinatoire 54 (2007), Article B54m.

[8] P. Leroux, “Enumerative problems inspired by Mayer’s theory of cluster integrals.“ The Electronic Journal of Combinatorics 11(1) (2004), Article R32.

[9] J. E. Mayer and M. G. Mayer, Statistical Mechanics. New York: Wiley (1940).

[10] F. H. Ree and W. G. Hoover, “Fifth and sixth virial coefficients for hard spheres and hard discs.” The Journal of Chemical Physics 40 (1964), 939–950.

[11] F. H. Ree and W. G. Hoover, “Reformulation of the virial series for classical fluids.” The Journal of Chemical Physics 41 (1964), 1635–1645.

[12] F. H. Ree and W. G. Hoover, “Seventh virial coefficients for hard spheres and hard discs.” The Journal of Chemical Physics 46 (1967), 4181–4196.

[13] R. J. Riddell and G. E. Uhlenbeck, “On the Theory of the virial development of the equation of state of monoatomic gases.” The Journal of Chemical Physics 21 (1953), 2056–2064.

[14] D. Ruelle, Statistical mechanics, Addison-Wesley (1989).

[15] R. P. Stanley, Enumerative Combinatorics, vol. 1, Belmont, California: Wadsworth (1986).

[16] G. E. Uhlenbeck and G. W. Ford, Lectures in Statistical Mechanics, Providence, Rhode Island: American Mathematical Society (1963), 181 pp.

LaCIM, Université du Québec à Montréal, CP 8888, Succ. Centre-ville, Montréal (Québec) H3C 3P8