Séminaire Lotharingien de Combinatoire 79 (2020), Article B79e

GRAPH WEIGHTS ARISING FROM STATISTICAL MECHANICS

AMEL KAOUCHE

Université de Moncton, Campus d’Edmudston, Canada

Abstract. In statistical mechanics it is well known that the coefficients of the virial expansion for a non-ideal gas are computed using the Mayer weight of 2-connected graphs. We study 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. Our results are new formulas of Mayer weights and Ree–Hoover weights for special infinite families of 2-connected graphs.

Résumé. En mécanique statistique, il est bien connu que les coefficients du développement du viriel pour un gaz non-idéal sont calculés en utilisant le poids de Mayer des graphes 2-connexes. Nous étudions le second poids de Mayer w_{M}(c) et de Ree–Hoover w_{RH}(c) d’un graphe 2-connexe c dans le cas d’un gaz à noyaux durs en dimension un. Ces poids sont calculés à partir des volumes signés de polytopes convexes associés naturellement au graphe c. Nous donnons des nouvelles formules pour le poids de Mayer et de Ree–Hoover pour des familles spéciales infinies de graphes 2-connexes.

1. Introduction

In the present paper, we study Graph weights in the context of a non-ideal gas in a vessel V ⊆ ℝ^{d}. In this case, the Second Mayer weight w_{M}(c) of a connected graph c, over the set [n] = {1, 2, …, n} of vertices, is defined by (see [5, 8, 9, 12])

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 a real-valued function associated with the pairwise interaction potential of the particles, see [21, 12].

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 [12]):

\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). 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] denotes 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 [15] 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 [15, 16, 17] 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).

The main goal of the present paper is to give new explicit formulas for the Mayer and Ree–Hoover weights of certain infinite families of graphs in the context of the hard core continuum gas, defined by (7), in dimension d = 1. The values w_{M}(c) and w_{RH}(c) for all 2-connected graphs c of size at most 8 are given in [5, 6]. In Section 2, we 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 [15, 16]. The interest of using the Ree–Hoover weight is that it has the value zero for many graphs. Section 3 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. A decomposition of the polytope P(c) into a certain number of simplices is exploited. This method was introduced in [12] and was adapted in [5, 9] to the context of Ree–Hoover weights and is called the method of graph homomorphisms. The explicit computation of Mayer or Ree–Hoover weights of particular graphs is very difficult in general and has only been made for certain specific families of graphs (see [7, 8, 9, 10, 11, 12]). In the present paper we extend this list to other graphs. We give new explicit formulas of the Ree–Hoover weight of these graphs in Section 4. Section 5 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 by e(g). If e is an edge of g (i.e., e ∈ g), g\e denote the graph obtained from g by removing the edge e. 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.

2. Relations between Mayer weight and Ree–Hoover weight

An important rewriting of the virial coefficients was performed by Ree and Hoover [15, 16] 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 weight series, vertices in the resulting graphs will all be mutually connected by either f bonds (solid lines) or \overline{f} bonds (dotted lines). In general, using Möbius inversion, it is easy to state formulas linking the two weights w_{M} and w_{RH}. These formulas are implicit in [16].

Proposition 1 ([9]). For a 2-connected graph b, we have

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

Proof. See [9]. □

Consequently, the virial coefficient can be rewritten in the form

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

for appropriate coefficients a_{n}(b) called the star content of the graph b. The importance of (12) is due to the fact that a_{n}(b) = 0 or w_{RH}(b) = 0 for many graphs b. This greatly simplifies the computation of β_{n}.

Using the definition of the Ree–Hoover weight, we have

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

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, (14)

and the Ree–Hoover’s 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},

(15)

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 for all {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 for all {i, j} ∈ c,

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

3.1. Sufficient conditions for w_{RH} = 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 guarantee the vanishing of their Ree–Hoover weights (see [5]). We introduce first some variants of the notion of subgraph and then state an associated lemma. Definition 2. 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′},  (16)

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 3 ([9]). 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 imply w_{RH}(g) = 0.  (17)

Proof. See [9]. □ Theorem 4 ([9]). 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 chordal : C_{k} \overline{⊆} g, k ≥ 4,  (18)
or g is claw-free : S_{3} \overline{⊆} g,  (19)

where S_{3} is the 3-star graph (see Figure 1) and C_{k} is the cycle on k elements.

3  1 n 2

Figure 1. The graph S_{3}

Proof. See [9]. □

3.2. Graph homomorphisms. The method of graph homomorphisms was introduced by Labelle, Leroux and Ducharme [12] for the exact computation of the Mayer weight w_{M}(b) of an arbitrary 2-connected graph b in the context of hardcore continuum gas in one dimension and was adapted by Kaouche and Leroux [5, 9] to the context of Ree–Hoover weights. 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 with 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 with 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, with 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 zero 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 → ℤ denotes 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}, (20)

and it is shown in [12] (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 (20) 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 configuration space ℝ^{n−1} × \{0\}.

Using the fractional coordinates to represent the centre of gravity X_{h,β} of the simplex P(h, β), and drawing a line segment connecting 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 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 5 ([12]). 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. (21)

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 6 ([12]). Let b be a 2-connected graph and let ν(b) be the number of pairs (h, β) such that the condition (21) is satisfied. Then the volume of the polytope P(b) is given by

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

Proposition 6 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 fashion we can adapt the above configurations to the context of the Ree–Hoover weight.

Proposition 7 ([9]). 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,  (23)
for any edge \{i, j\} of \overline{b}, β(i) < β(j) implies h_{i} ≤ h_{j} − 1 or h_{i} ≥ h_{j} + 2. (24)

Proof. See [9]. □

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

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

Proof. See [9]. □

Proposition 8 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 new 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 homomorphism and Theorem 4. The weights of 2-connected graphs b are given in absolute value |w(b)|, the sign being always equal to (−1)^{e(b)}.

Lemma 9. 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 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}\C_{k}. Let C_{k} denote the cycle on k elements. For the special case k = 4 corresponding to the graph K_{n}\C_{4} the proof is different from the one corresponding to the case k ≥ 5.

Proposition 10 ([9]). For n ≥ 6, we have

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

where C_{4} is the unoriented cycle with 4 vertices (see Figure 3).

Figure 3. The graph C_{4}

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

w_{RH}(K_{n}\C_{k}) = 0.  (27)

Proof. Equation (27) is a consequence of Theorem 4. Indeed, C_{4} \overline{⊆} K_{n}\C_{k}, for k ≥ 5, n ≥ k + 1 and we conclude using (18). □

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

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

Let us start with the simple case S_{2} · C_{4} · S_{1}.

Proposition 12. For n ≥ 8, we have

|w_{RH}(K_{n}\(S_{2} · C_{4} · S_{1}))| = \frac{4}{(n − 1)(n − 2) ⋯ (n − 6)}.  (28)

Proof. We can assume that the missing edges are {1, n}, {2, n}, {4, n}, {1, 3}, {1, 5}, {1, 7} and {2, 3} (see Figure 5).

13  2n  4 57
Figure 5. The graph S_{2} · C_{4} · S_{1}

According to Lemma 9 there are two possibilities for h:

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

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

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

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

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

□

In the general case we have the following result.

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

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

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

13  2  4 n  6 57
Figure 7. The graph S_{2} · C_{4} · S_{2}

According to Lemma 9 there are two possibilities for h:

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

j + 2} and β(3) = k + 1 and β(2) = k + 2 and β(1) = k + j + 3,

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

β(1) = n − k − j − 3.

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

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

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

□

4.3. The Ree–Hoover weight of the graph K_{n}\(S_{k} · K_{3}). Let S_{k} · K_{3} denote the graph obtained by identifying one vertex of the graph K_{3} with the centre of a k-star. See Figure 9 for an example. w_{RH}(K_{n}\(S_{k} · K_{3})) = 0, for k ≥ 0, n ≥ k + 5, which is a consequence of Theorem 4. Note that the special case k = 0 corresponding to the graph K_{n}\K_{3}.

4.4. The Ree–Hoover weight of the graph K_{n}\(S_{k} · C_{p}). Let S_{k} · C_{p} denote the graph obtained by identifying one vertex of the graph C_{p} with the centre of a k-star. See Figure 10 for an example. w_{RH}(K_{n}\(S_{k} · C_{p})) = 0, for p ≥ 5, k ≥ 1, n ≥ k + p, which is a consequence of Theorem 4.

Figure 9. The graph S_{4} · K_{3}

Figure 10. The graph S_{4} · C_{5}

4.5. The Ree–Hoover weight of the graph K_{n}\kS_{1}. For k ≥ 2, n ≥ 2k, let K_{n}\kS_{1} denote the complete graph on n vertices from which k separate edges have been removed, with S_{1} = e is the graph with only one edge. See Figure 11 for an example. Then we have w_{RH}(K_{n}\kS_{1}) = w_{RH}(K_{n}\ke) = 0, which is a consequence of Theorem 4.

Figure 11. The graph 3S_{1}

Note that, for k = 1, we have the following result.

Proposition 14 ([9]). 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)| = |w_{RH}(K_{n}\S_{1})| = \frac{2}{(n − 1)}·  (30)

Proof. See [9]. □

Note that the formula (30) is a special case of (31).

4.6. The Ree–Hoover weight of the graph K_{n}\(S_{j} ·K_{3} ·S_{k}). Let (S_{j} ·K_{3} ·S_{k}) denote the graph obtained by joining with an edge of the graph K_{3} the centres of a j-star and of a k-star. See Figure 12 for an example. w_{RH}(K_{n}\(S_{j} ·K_{3}·S_{k})) = 0, for j ≥ k ≥ 1, n ≥ k + j + 4, which is a consequence of Theorem 4.

Figure 12. The graph S_{3} · K_{3} · S_{4}

4.7. The Ree–Hoover weight of the graph K_{n}\(S_{j} ·C_{p} ·S_{k}). Let (S_{j} ·C_{p} ·S_{k}) denote the graph obtained by joining with an edge of the graph C_{p} the centres of a j-star and of a k-star. See Figure 13 for an example. w_{RH}(K_{n}\(S_{j} ·C_{p}·S_{k})) = 0, for p ≥ 5, j ≥ k ≥ 1, n ≥ k + j + p + 1, which is a consequence of Theorem 4.

Figure 13. The graph S_{2} · C_{6} · S_{4}

We need to use Propositions 15–17 to prove Mayer’s weight formulas that will be presented in Section 5.

4.8. 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}}, (see Figure 14, for the case of S_{3}).

3  1 n 2

Figure 14. The graph S_{3}

Proposition 15 ([9]). For k ≥ 1, n ≥ k + 3, we have

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

4.9. 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 centres of a j-star and of a k-star. See Figure 15 for an example.

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

Proposition 16 ([9]). 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))}.  (32)

4.10. 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 centre of a k-star. See Figure 16 for an example.

Proposition 17 ([9]). 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))}.  (33)

Note that the formula (33) is not a special case of (29).

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

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 formula

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

which is a consequence of (11) 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 gas in one dimension. Substituting K_{n}\g and K_{n}\k for b and d in (34), we have

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

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}\C_{k}.

Proposition 18 ([9]). For k = 4, 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)}. (36)

Proposition 19. For n ≥ k ≥ 5 we have

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

Proof. The supergraphs of K_{n}\C_{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}\(S_{1}–S_{1}) and K_{n}. Their multiplicities are given by the formula

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

We conclude using Propositions 15 and 16. □

Note that the formula (36) is not a special case of (37).

5.2. The Mayer weight of the graph K_{n}\(S_{j} · C_{4} · S_{k}).

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

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

+ \frac{8}{(n − 1) (n − 2)} + \frac{10}{(n − 1) (n − 2) (n − 3)}

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

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

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

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

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

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

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

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

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

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

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

We conclude using Propositions 10 and 13–17. □

5.3. The Mayer weight of the graph K_{n}\(S_{k} · K_{3}).

Proposition 21. For k ≥ 0, n ≥ k + 5, we have

|w_{M}(K_{n}\(S_{k} · K_{3})| = 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 − 2)}

+ \frac{2}{(n − 1)} + \frac{8}{(n − 1)(n − 2)}.

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

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

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

+ |w_{RH}(K_{n}\S_{1})| + 2|w_{RH}(K_{n}\S_{2})|.

We conclude using Propositions 15 and 16. □

For the special case k = 0, n ≥ 5, we have

|w_{M}(K_{n}\K_{3})| = n + \frac{6}{(n − 1)} + \frac{12}{(n − 1)(n − 2)}.  (38)

5.4. The Mayer weight of the graph K_{n}\(S_{k} · C_{p}).

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

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

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

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

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

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

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

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

We conclude using Propositions 15 and 16. □

5.5. The Mayer weight of the graph K_{n}\(S_{j} · K_{3} · S_{k}).

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

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

− \frac{2}{(n − 1)} + \frac{4}{(n − 1) (n − 2)}

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

+ ∑_{m=1}^{j+1} ∑_{l=1}^{j} 2 [\binom{j}{m}\binom{k}{l} + \binom{j}{m − 1}\binom{k}{l} + \binom{j}{l}\binom{k}{m − 1}]

· \frac{m! l!}{(n − 1) ⋯ (n − m − l − 1)}.

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

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

− |w_{RH}(K_{n}\S_{1})| + |w_{RH}(K_{n}\S_{2})|

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

+ ∑_{m=1}^{j+1} ∑_{l=1}^{j} [\binom{j}{m}\binom{k}{l} + \binom{j}{m − 1}\binom{k}{l} + \binom{j}{l}\binom{k}{m − 1}]

· |w_{RH}(K_{n}\(S_{m} − S_{l}))|.

We conclude using Propositions 15 and 16. □

5.6. The Mayer weight of the graph K_{n}\(S_{j} · C_{p} · S_{k}).

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

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

+ \frac{2(p − 4)}{(n − 1)} + \frac{4(p − 2)}{(n − 1) (n − 2)} + \frac{2(p − 3)}{(n − 1) (n − 2) (n − 3)}

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

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

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

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

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

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

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

We conclude using Propositions 15 and 16. □

5.7. The Mayer weight of the graph K_{n}\kS_{1}.

Proposition 25. For k ≥ 1, n ≥ 2k, we have

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

Proof. The supergraphs of K_{n}\kS_{1}, k ≥ 1, whose Ree–Hoover weight is not zero are up to isomorphism of the form K_{n}\S_{1} and K_{n}. Their multiplicities are given by the formula

|w_{M}(K_{n}\kS_{1})| = |w_{RH}(K_{n})| + k|w_{RH}(K_{n}\S_{1})|.

We conclude using Proposition 15. □

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.” Ph.D. thesis, Stony Brook University, Stony Brook, New York (2004).

[5] A. Kaouche, “Invariants de graphes liés aux gaz imparfaits.” Publications du Laboratoire de Combinatoire et d’Informatique Mathématique (LaCIM), vol. 42 (2010).

[6] A. Kaouche, “Valeurs des poids de Mayer et des poids de Ree–Hoover pour tous les graphes 2-connexes de taille au plus 7 et leurs paramètres descriptifs.”

http://professeure.umoncton.ca/umce-kaouche amel/files/umce-kaouche amel/
wf/wf/TableauRH7.pdf

“Valeurs des poids de Mayer et des poids de Ree–Hoover pour tous les graphes 2-connexes de taille 8 et leurs paramètres descriptifs.”

http://professeure.umoncton.ca/umce-kaouche amel/files/umce-kaouche amel/
wf/wf/TableauRH8.pdf (2016).

[7] A. Kaouche, G. Labelle, “Mayer polytopes and divided differences.” Workshop on “Combinatorial Identities and Their Applications in Statistical Mechanics”, 2008, Isaac Newton Institute, University of Cambridge,

http://www.newton.ac.uk/webseminars/pg+ws/2008/csm/csmw03/.

[8] A. Kaouche, P. Leroux, “Graph weights arising from Mayer and Ree–Hoover theories.” Discrete Mathematics & Theoretical Computer Science Proceedings, 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008), AJ, 2008, pp. 259–270.

[9] A. Kaouche, P. Leroux, “Mayer and Ree–Hoover weights of infinite families of 2-connected graphs.” Séminaire Lotharingien de Combinatoire, 61A (2009), Article B61Af.

[10] A. Kaouche, G. Labelle, “Mayer and Ree–Hoover weights, graphs invariants and bipartite complete graphs.” Pure Mathematics and Applications, 24(1) (2013), 19–29.

[11] A. Kaouche, G. Labelle, “Poids de Mayer et transformées de Fourier.” Annales Mathématiques du Québec, 38(1) (2014), 37–59.

[12] 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.

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

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

[15] 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.

[16] F. H. Ree and W. G. Hoover, “Reformulation of the Virial Series for Classical Fluids.” The Journal of Chemical Physics, 41 (1964), 1635–1645.

[17] 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.

[18] 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.

[19] D. Ruelle, Statistical Mechanics. Addison–Wesley (1989).

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

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

Université de Moncton, Campus d’Edmudston, Canada