Séminaire Lotharingien de Combinatoire 74 (2017), Article B74e

GEODESICS IN A GRAPH OF PERFECT MATCHINGS

ROY H. JENNINGS

Abstract. Let 𝒫_{m} be the graph on the set of perfect matchings in the complete graph K_{2m}, where two perfect matchings are connected by an edge if their symmetric difference is a cycle of length four. This paper studies geodesics in 𝒫_{m}. The diameter of 𝒫_{m}, as well as the eccentricity of each vertex, are shown to be m − 1. Two proofs are given to show that the number of geodesics between any two antipodes is m^{m−2}. The first is a direct proof via a recursive formula, and the second is via reduction to the number of minimal factorizations of a given m-cycle in the symmetric group S_{m}. An explicit formula for the number of geodesics between any two matchings in 𝒫_{m} is also given.

Let ℳ_{m} be the graph on the set of non-crossing perfect matchings of 2m labeled points on a circle with the same adjacency condition as in 𝒫_{m}. ℳ_{m} is an induced subgraph of 𝒫_{m}, and it is shown that ℳ_{m} has exactly one pair of antipodes having the maximal number m^{m−2} of geodesics between them.

1. Introduction

Consider a set of 2m labeled points on a circle. Join its points in disjoint pairs by m straight line segments, such that no two lines intersect. Abstractly, this is a perfect matching in the complete graph K_{2m}. Such a matching is called a non-crossing perfect matching. Hernando, Hurtado and Noy defined in [8] the graph of non-crossing perfect matchings ℳ_{m}, in which two matchings are connected by an edge if their symmetric difference is a cycle of length four. They showed that the diameter and the eccentricity of every vertex in this graph are m − 1.

This paper studies the graph 𝒫_{m} on the set of all perfect matchings in the complete graph K_{2m} where two matchings are connected by an edge if their symmetric difference is a cycle of length four.

The distance between any two matchings in 𝒫_{m} is shown to depend only on the number of components in their union.

Theorem (Theorem 3.4). For any M_{1}, M_{2} ∈ 𝒫_{m}, d(M_{1}, M_{2}) = m − l, where l is the number of components in M_{1} ∪ M_{2}.

Although 𝒫_{m} is larger than the graph of non-crossing perfect matchings ℳ_{m}, which is an induced subgraph of 𝒫_{m}, it is shown that the two graphs still share the same diameter, and that it is equal to the eccentricity of all of their vertices.

Theorem (Corollary 3.5). The diameter of 𝒫_{m}, as well as the eccentricity of every vertex in it, is m − 1.

Enumeration of the number of geodesics (shortest paths) between antipodes in 𝒫_{m} reveals the following surprising result.

Theorem (Corollary 4.5). The number of geodesics between any two antipodes in 𝒫_{m} is m^{m−2}.

The expression m^{m−2} appears in Cayley’s well known formula for the number of labeled trees on m vertices. On the other hand, Hurwitz [9] (see also [12]) showed that it gives as well the number of factorizations of a given m-cycle as a product of m − 1 transpositions in S_{m}. (Bijections between these trees and factorizations appear, e.g., in [7, 11].) In Section 5, an alternative proof, suggested by Y. Roichman, for Corollary 4.5 is provided via reduction to the number of factorizations of a given m-cycle as a product of m − 1 transpositions.

An explicit formula for the number of geodesics between any two matchings in 𝒫_{m} is given in Corollary 4.6.

Corollary 4.5 does not hold for the subgraph ℳ_{m}. Instead, we have the following result.

Theorem (Theorem 4.7). The graph ℳ_{m} of non-crossing perfect matchings has a unique pair of matchings with m^{m−2} geodesics between them. All other pairs have a smaller number of geodesics.

This paper is based on the author’s M.Sc. thesis. For generalizations and extensions of results in this paper see [2, 3, 6].

2. The Graph of Perfect Matchings

Consider the set of all perfect matchings in the complete graph K_{2m}. Denote the graph of perfect matchings on this set, in which two distinct matchings M_{1} and M_{2} are connected by an edge if their symmetric difference is a cycle of length four, by 𝒫_{m}. Here, the symmetric difference of M_{1} and M_{2}, is the graph consisting of the edges that belong to exactly one of these matchings. In this paper, all matchings are perfect, and thus the term perfect is freely omitted. Denote adjacent matchings in 𝒫_{m} by M_{1} ∼ M_{2}, and write M_{1} ≃ M_{2} if either M_{1} = M_{2} or M_{1} ∼ M_{2}.

⟷

Figure 1. Adjacent matchings in 𝒫_{4}

Fact 2.1. The cardinality of 𝒫_{m} is the double factorial:

|𝒫_{m}| = (2m − 1)!! = (2m − 1) · (2m − 3) · . . . · 1.

For any edge e = (v_{1}, v_{2}) in the complete graph K_{2m} and a matching M in 𝒫_{m}, the insertion of the edge e into the matching M, denoted by M ∗ e, is defined as follows: If e is already in M, then M ∗ e = M. Otherwise, if (v_{1}, v_{3}) and (v_{2}, v_{4}) are the edges in M incident with v_{1} and v_{2}, then M ∗ (v_{1}, v_{2}) is the matching obtained from M by deleting (v_{1}, v_{3}) and (v_{2}, v_{4}) and adding (v_{1}, v_{2}) and (v_{3}, v_{4}).

Extend the definition recursively:

M ∗ (e_{1}, …, e_{n}) = (M ∗ (e_{1}, …, e_{n−1})) ∗ e_{n}.

Observation 2.2. Two distinct matchings M_{1} and M_{2} in 𝒫_{m} are adjacent if and only if M_{2} = M_{1} ∗ e, for some edge e not in M_{1}.

Remark 2.3. Let M be a matching in 𝒫_{m}. By definition, every neighbor of M misses exactly two edges of M. Conversely, for each pair of distinct edges in M, there are exactly two neighbors of M not containing this pair. Therefore, 𝒫_{m} is a regular graph of degree 2\binom{m}{2}.

Proposition 2.4. Let M be a matching in 𝒫_{m}, and let (e_{1}, …, e_{m}) be the edges of M arranged in any order. For any matching M′ in 𝒫_{m}, M = M′ ∗ (e_{1}, …, e_{m}).

Indeed, the edges inserted into M′ are vertex disjoint, and therefore they all belong to the final matching.

Corollary 2.5. The graph of perfect matchings 𝒫_{m} is connected.

3. Geodesics and Diameter

Recall that a geodesic between two vertices in a connected graph is a shortest path between them. The distance between two vertices u and v, denoted by d(u, v), is the length of a geodesic between them. The eccentricity of a vertex is the maximal distance between this vertex and any other vertex. The maximal length of a geodesic in a connected graph is called the graph’s diameter. If the distance between two vertices is the graph’s diameter, then the vertices are called antipodes.

Hernando, Hurtado and Noy [8] found a formula for the distance between two matchings in the graph ℳ_{m} of non-crossing perfect matchings with m edges, implying that the diameter of this graph and the eccentricity of every vertex in it are m − 1. In this section, it is shown that, although 𝒫_{m} is larger than the graph of non-crossing perfect matchings, where the latter is an induced subgraph, the diameter and the eccentricity of every vertex in it remain m − 1.

Fact 3.1. The union of two matchings M_{1} and M_{2} in 𝒫_{m} is a vertexdisjoint union of alternating cycles C_{i} of even length (a common edge is considered as a cycle of length two):

M_{1} ∪ M_{2} = C_{1} ˙∪ C_{2} ˙∪ … ˙∪ C_{l} .

Observation 3.2. Denote the number of connected components in a graph G by c(G). Given two matchings M_{1}, M_{2} ∈ 𝒫_{m} and an edge e ∉ M_{1}, exactly one of the following cases holds:

(1) c(M_{1} ∗ e ∪ M_{2}) = c(M_{1} ∪ M_{2}) − 1. This is the case if and only if the vertices of e belong to two different cycles in M_{1} ∪ M_{2}.

(2) c(M_{1} ∗ e ∪ M_{2}) = c(M_{1} ∪ M_{2}) + 1. This is the case if and only if the vertices of e belong to the same cycle in M_{1} ∪ M_{2}, and the insertion of e into M_{1} splits this cycle into two cycles in M_{1} ∗ e ∪ M_{2}.

(3) c(M_{1} ∗ e ∪ M_{2}) = c(M_{1} ∪ M_{2}). This is the case if and only if the vertices of e belong to the same cycle in M_{1} ∪ M_{2}, and the insertion of e into M_{1} does not split this cycle in M_{1} ∗ e ∪ M_{2}.

Remark 3.3. In the settings of Observation 3.2, every pair of distinct edges in M_{1} that belong to different components in M_{1} ∪ M_{2}, corresponds to two unique neighbors of M_{1} that belong to the first case of the observation. Moreover, every pair of distinct edges in M_{1} that belongs to the same component in M_{1} ∪ M_{2} corresponds to one unique neighbor of M_{1} that belongs to the second case of the observation, and one unique neighbor that belongs to the third case.

Theorem 3.4. For any M_{1}, M_{2} ∈ 𝒫_{m}, d(M_{1}, M_{2}) = m − l, where l is the number of components in M_{1} ∪ M_{2}.

Proof. Note that m−l = 0 if and only if M_{1} = M_{2}. By Observation 3.2, |c(M′ ∪ M_{2}) − c(M ∪ M_{2})| ≤ 1 for any two neighbors M ∼ M′ in 𝒫_{m}. Thus d(M_{1}, M_{2}) ≥ m − l. For every matching M ≠ M_{2}, there is some alternating cycle C ⊆ M ∪ M_{2} such that |C| ≥ 4. Therefore, by Remark 3.3, for every pair of distinct edges in M ∩ C, M has a unique neighbor M′ such that c(M′ ∪ M_{2}) − c(M ∪ M_{2}) = 1. Thus, d(M_{1}, M_{2}) ≤ m − l. □

By Theorem 3.4, antipodes in 𝒫_{m} are pairs of matchings whose union consists of one cycle.

Corollary 3.5. The diameter of 𝒫_{m}, as well as the eccentricity of every vertex in it, are m−1. The number of antipodes of every matching is (2m − 2)!!.

Remark 3.6. An analogue of Theorem 3.4 for the graph ℳ_{m} of noncrossing perfect matchings appears in [8], in the equivalent form

d(M_{1}, M_{2}) = \frac{1}{2} ∑_{i=1}^{l} (length(C_{i}) − 2) .

4. Counting Geodesics

In this section, the number of geodesics between any two matchings in 𝒫_{m} is given. In particular, the number of geodesics between antipodes is shown to be m^{m−2}. The section concludes by showing that in the subgraph ℳ_{m} of non-crossing perfect matchings, there is exactly one pair of antipodes having the maximal number m^{m−2} of geodesics between them.

Definition 4.1. Denote the number of geodesics between two matchings, whose symmetric difference is one cycle of length 2k, by P_{2k}, for k ≥ 2. Define P_{2} = 1.

Theorem 4.2. For every positive integer k, we have

P_{2k} = \frac{k}{2} ∑_{i=1}^{k−1} \binom{k − 2}{i − 1}P_{2i}P_{2k−2i}, for k ≥ 2,

with P_{2} = 1.

Proof. Let M_{1}, M_{2} ∈ 𝒫_{m}, m ≥ k, be two matchings with a symmetric difference of one cycle of length 2k. Denote this cycle by C. M_{1}∪M_{2} has m − k + 1 components (m − k components of size 2 and one component of size 2k). Therefore, by Theorem 3.4, d(M_{1}, M_{2}) = k − 1.

By Remark 3.3 and Theorem 3.4, a neighbor M′ of M_{1} is in some geodesic between M_{1} and M_{2} if and only if C splits in M′ ∪ M_{2} into two cycles. The lengths of these two cycles are 2i and 2k − 2i for some i with 1 ≤ i ≤ \frac{k}{2}. Therefore, the number of geodesics from M_{1} to M_{2}, beginning with M′, is \binom{k−2}{i−1}P_{2i}P_{2k−2i}, where the binomial coefficient \binom{k−2}{i−1} counts the ways to interlace the remaining k−2 insertions between the two cycles.

For every 1 ≤ i < \frac{k}{2}, there are exactly k neighbors of M_{1} in which C splits into two cycles of length 2i and 2k − 2i as above. If k is even, then for i = \frac{k}{2} there are exactly \frac{k}{2} neighbors of M_{1} in which C splits into two cycles of length k as above. Therefore, the formula k ∑_{i=1}^{k−1} \binom{k−2}{i−1}P_{2i}P_{2k−2i} counts every geodesic twice, leading to the claimed result. □

The following is a reformulation of Theorem 4.2, and its proof was suggested by R. Adin.

Lemma 4.3. For every positive integer k, we have

P_{2k} = ∑_{i=1}^{k−1} i\binom{k − 2}{i − 1}P_{2i}P_{2k−2i},

with P_{2} = 1.

Proof. Write a_{i} = i\binom{k−2}{i−1}P_{2i}P_{2k−2i}. The symmetry of the binomial coefficients \binom{k−2}{i−1} = \binom{k−2}{k−i−1} implies

2 ∑_{i=1}^{k−1} a_{i} = ∑_{i=1}^{k−1} a_{i} + ∑_{i=1}^{k−1} a_{k−i}

= ∑_{i=1}^{k−1} (i\binom{k − 2}{i − 1}P_{2i}P_{2k−2i}

+(k − i)\binom{k − 2}{k − i − 1}P_{2(k−i)}P_{2k−2(k−i)})

= ∑_{i=1}^{k−1} (i\binom{k − 2}{i − 1}P_{2i}P_{2k−2i} + (k − i)\binom{k − 2}{i − 1}P_{2k−2i}P_{2i})

= k ∑_{i=1}^{k−1} \binom{k − 2}{i − 1}P_{2i}P_{2k−2i}

= 2P_{2k}.

The last equation is essentially Theorem 4.2. □

Corollary 4.4. For every positive integer k, we have P_{2k} = k^{k−2}.

Proof. By the well known Cayley Formula [5], the number of labeled trees on k vertices is T_{k} = k^{k−2}. By [10, Ex. 6, p. 34 and pp. 249– 250], we have T_{k} = ∑_{i=1}^{k−1} i\binom{k−2}{i−1}T_{i}T_{k−i}, with T_{1} = 1. Comparison with Lemma 4.3 concludes the proof. □

By Theorem 3.4, antipodes in 𝒫_{m} are pairs of matchings with a symmetric difference of one cycle of length 2m.

Corollary 4.5. The number of geodesics between antipodes in 𝒫_{m} is m^{m−2}.

Corollary 4.5 can be generalized to count the number of geodesics between any two matchings in 𝒫_{m}.

Corollary 4.6. Let M_{1}, M_{2} ∈ 𝒫_{m} with M_{1}∪M_{2} = C_{1} ˙∪ C_{2} ˙∪ ⋯ ˙∪ C_{l}, as in Fact 3.1. The number of geodesics between M_{1} and M_{2} is

\binom{m − l}{n(C_{1}), …, n(C_{l})} ∏_{i=1}^{l} (n(C_{i}) + 1)^{n(C_{i})−1} ,

where n(C_{i}) = \frac{length(C_{i})}{2} − 1.

Proof. n(C_{i}) is the number of insertions within the cycle C_{i}. The binomial coefficient \binom{m−l}{n(C_{1}),...,n(C_{l})} counts the ways to interlace insertions between the cycles. □

The analogue of Corollary 4.5 for the induced subgraph in 𝒫_{m} of non-crossing perfect matchings ℳ_{m}, is the following.

Theorem 4.7. The graph ℳ_{m} of non-crossing perfect matchings has a unique pair of matchings with m^{m−2} geodesics between them. All other pairs have a smaller number of geodesics.

Proof. ℳ_{m} consists of matchings on a set of 2m points on a circle. Denote the convex hull of these points by H. We show that the two matchings having all their edges on the boundary of H are the only pair of antipodes in ℳ_{m} with m^{m−2} geodesics between them. All other pairs have a smaller number of geodesics.

Let M_{1} and M_{2} be the two matchings in ℳ_{m} having all their edges on the boundary of H. By Remark 3.6, M_{1} and M_{2} are antipodes in ℳ_{m}. By Theorem 3.4, they are also antipodes in 𝒫_{m}. Let P = (M_{1} = M′_{1}, M′_{2}, …, M′_{d} = M_{2}) be a geodesic between M_{1} and M_{2}. Since M′_{1} ∪ M′_{d} has one component, by Theorem 3.4, M′_{2} ∪ M′_{d} is a union of two vertex-disjoint alternating cycles. It is clear that these cycles are the boundaries of two disjoint polygons (including the case of a shared edge, which is a convex polygon with two vertices). Therefore, M′_{2} is also in ℳ_{m}. Similarly, for every M′_{i} ∈ P, 2 ≤ i ≤ d, some convex polygon in M′_{i−1} ∪ M′_{d}, is split into two disjoint convex polygons in M′_{i} ∪ M′_{d}. Thus, P is contained in ℳ_{m}, and the number of geodesics between M_{1} and M_{2} in ℳ_{m} is m^{m−2}.

For any other pair M_{1} and M_{2} of antipodes in ℳ_{m}, one of the matchings, say M_{1}, has an edge e contained (except for its endpoints) in the interior of H. Denote the two components of H \ e by H_{1} and H_{2}. M_{1} must have at least one edge e_{1} contained in H_{1} and another e_{2} contained in H_{2}. Let e′ be an edge incident with a vertex of e_{1} and a vertex of e_{2} such that the cycle M_{1} ∪M_{2} splits in (M_{1} ∗e′)∪M_{2} into two cycles. Then M_{1} ∗ e′ is a neighbor of M_{1} in a geodesic between M_{1} and M_{2} in 𝒫_{m}. Since e and e′ intersect, M_{1} ∗ e′ ∉ ℳ_{m}. Thus, the number of geodesics between M_{1} and M_{2} in ℳ_{m} is smaller than m^{m−2}. □

5. Factorization of Permutations by Transpositions

Let S_{m} be the symmetric group on m elements. A minimal factorization by transpositions (or, simply, minimal factorization) of a permutation π ∈ S_{m}, is a product σ_{1} ⋯ σ_{n} of a minimal number of transpositions, such that π = σ_{1} ⋯ σ_{n}. In this section, the number of geodesics between antipodes in 𝒫_{m} is shown to be equal to the number of minimal factorizations of an m-cycle in S_{m}. It follows from a result of Hurwitz [9], as explained by Strehl [12], and Cayley’s classical formula [5] that the latter number is the same as the number of labeled trees on m vertices. Bijections which explain this coincidence directly can be, e.g., found in [7, 11].

Throughout this section, the vertices of the underlying complete graph K_{2m} of 𝒫_{m}, are labeled by {1, −1, …, m, −m}. Denote the complete bipartite graph with bipartition of vertices {1, …, m} and {−1, …, −m} by K_{m,m}. Denote the subgraph of 𝒫_{m}, induced by the perfect matchings of K_{m,m}, by 𝒫_{m,m}. Matchings in 𝒫_{m,m} correspond naturally to permutations in S_{m}, by identifying a matching π ∈ 𝒫_{m,m} with a permutation π′ ∈ S_{m} such that π′(i) = j for every (i, −j) ∈ π. Using this correspondence, a matching π ∈ 𝒫_{m,m} will also be referred to as a permutation in S_{m} (and vice versa).

Observation 5.1. Let π ∈ 𝒫_{m,m}. For 1 ≤ i ≤ j ≤ m, we have

π ∘ (i, j) = π ∗ (i, −π(j)) = π ∗ (j, −π(i)),

where (i, i) is understood as the identity of S_{m}.

In Observation 5.1, the neighbor π ∗ (i, −π(j)) = π ∗ (j, −π(i)) of π in 𝒫_{m,m} is one of the two neighbors of π in 𝒫_{m}, corresponding to the choice of the two edges (i, −π(i)) and (j, −π(j)), as in Remark 2.3. The other neighbor in 𝒫_{m}, corresponding to this choice of two edges, is not in 𝒫_{m,m}. Thus, every pair of edges in π corresponds to a unique neighbor of π in 𝒫_{m,m}, which also corresponds to right multiplication of π by a unique transposition in S_{m}. In other words, adjacency in 𝒫_{m,m} can be understood as right multiplication by transpositions.

Let G be a group, and let S be a symmetric (S^{−1} = S) generating set of G. Recall that the (right) Cayley graph X(G, S) is the directed graph on the elements of G, in which (g_{1}, g_{2}) is an edge if g_{1}s = g_{2} for some s in S.

Corollary 5.2. 𝒫_{m,m} is the underlying simple graph of the (right) Cayley graph X(S_{m}, S), where S is the set of all of the transpositions in S_{m}.

Observation 5.3. Let π and σ be two matchings in 𝒫_{m,m}, and let π ∗ e be a neighbor of π (in 𝒫_{m}) in a geodesic between π and σ. Then π ∗ e ∈ 𝒫_{m,m}.

Indeed, the union of π and σ, in Observation 5.3, is a vertex-disjoint union of alternating cycles of even lengths. Clearly, the signs of the labels of the vertices within each cycle alternate. By Observation 3.2 and Theorem 3.4, a neighbor π ∗ e of π in 𝒫_{m} is in some geodesic between π and σ if and only if a cycle in π ∪ σ is split into two cycles in π ∗ e ∪ σ. This implies that the vertices of e belong to the same cycle in π ∪ σ, and that their labels have different signs (see Figure 2).

\begin{matrix}- \\ + \\ - \\ + \\ - \\ + \\ - \\ + \\ e \\ π ∪ σ \end{matrix}  ⟶  \begin{matrix}- \\ + \\ - \\ + \\ - \\ + \\ - \\ + \\ π ∗ e ∪ σ \end{matrix}

Figure 2. Neighbors in a geodesic in 𝒫_{m,m}.

Here, the dotted edges belong to σ and the solid edges belong to π.

Corollary 5.4. Let π and σ be two matchings in 𝒫_{m,m}. Every geodesic between π and σ in 𝒫_{m} is contained in 𝒫_{m,m}.

By Corollaries 5.2 and 5.4, the number of geodesics in 𝒫_{m} between two elements π and σ in 𝒫_{m,m} is equal to the number of minimal factorizations of πσ^{−1}. In particular, by Theorem 3.4, an m-cycle π and the identity of S_{m} are antipodes in 𝒫_{m}, and the number of geodesics between them is equal to the number of minimal factorizations of π.

Corollary 5.5. The number of geodesics between antipodes in 𝒫_{m} is equal to the number of minimal factorizations of an m-cycle in S_{m}.

Hurwitz’s result was generalized to enumeration of maximal chains in the non-crossing partition lattice of any well-generated complex reflection group (see [4, Proposition 7.6]). Appropriate generalizations of Corollary 5.5 to other reflection groups are most desired.

6. Acknowledgments

I would like to thank my supervisors, Ron M. Adin and Yuval Roichman, for their guidance and help. I would also like to thank Christian Krattenthaler for his many valuable suggestions.

References

[1] R. M. Adin and Y. Roichman, On maximal chains in the non-crossing partition lattice, J. Combin. Theory Ser. A 125 (2014), 18–46.

[2] C. A. Athanasiadis and Y. Roichman, The absolute order of a permutation representation of a Coxeter group, J. Algebraic Combin. 39 (2014), 75–98.

[3] A. Avni, Matchings and permutations, M.Sc. Thesis, Bar-Ilan University, 2013.

[4] D. Bessis, Finite complex reflection arrangements are K(π, 1), Ann. Math. (2) 181 (2015), 809–904.

[5] A. Cayley, A theorem on trees, Quart. J. Math. 23 (1889), 376–378.

[6] M. Cohen and M. Teicher, Kauffman’s clock lattice as a graph of perfect matchings: a formula for its height, Electron. J. Combin. 21(4) (2014), Article 4.31, 39 pp.

[7] I. Goulden and A. Yong, Tree-like properties of cycle factorizations, J. Combin. Theory Ser. A 98 (2002), 106–117.

[8] C. Hernando, F. Hurtado and M. Noy, Graphs of non-crossing perfect matchings, Graphs Combin. 18 (2002), 517–532.

[9] A. Hurwitz, Über Riemannsche Flächen mit gegebenen Verzweigungspunkten, Math. Ann. 39 (1891), 1–61.

[10] L. Lovász. Combinatorial Problems and Exercises, corrected reprint of the 1993 second edition, American Mathematical Society Chelsea Publishing, Providence, R.I., 2007.

[11] P. Moszkowski, A solution to a problem of Dénes: A bijection between trees and factorizations of cyclic permutations, Europ. J. Combin. 10 (1989), 13–16.

[12] V. Strehl, Minimal transitive products of transpositions - the reconstruction of a proof of A. Hurwitz, Sém. Lothar. Combin. 37 (1996), Article B37c, 12 pp.

Department of Mathematics, Bar-Ilan University, Ramat-Gan 52900, Israel.

E-mail address: RoyHJennings@gmail.com