ars mathematica contemporanea
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 12 (2017) 205-217
An algebraic proof of the Erdos-Ko-Rado theorem for intersecting families of perfect
matchings
Chris Godsil *
Department of Combinatorics and Optimization, University of Waterloo Waterloo, Canada
Karen Meagher *
Department of Mathematics and Statistics, University of Regina Regina, Canada
Received 16 November 2015, accepted 20 July 2016, published online 5 December 2016
In this paper we give a proof that the largest set of perfect matchings, in which any two contain a common edge, is the set of all perfect matchings that contain a fixed edge. This is a version of the famous Erdos-Ko-Rado theorem for perfect matchings. The proof given in this paper is algebraic, we first determine the least eigenvalue of the perfect matching derangement graph and then use properties of the perfect matching polytope to prove the result.
Keywords: Perfect matching derangement graph, independent sets, Erdos-Ko-Rado theorem. Math. Subj. Class.: 05C35, 05C69
1 Introduction
A perfect matching in the complete graph K2k is a set of k vertex disjoint edges. Two perfect matchings intersect if they contain a common edge. In this paper we use an algebraic method to prove that the natural version of the Erdos-Ko-Rado (EKR) theorem holds for perfect matchings. This theorem shows that the largest set of perfect matchings, with the property that any two intersect, is the set of the all perfect matchings that contain a specific edge.
* Research supported by NSERC.
E-mail addresses: cgodsil@math.uwaterloo.ca (Chris Godsil), karen.meagher@uregina.ca (Karen Meagher)
Abstract
©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
206
Ars Math. Contemp. 12 (2017) 383-413
The algebraic method in this paper is similar to the proof that the natural version of the EKR theorem holds for permutations in [4]. In this paper we determine the least eigenvalue for the perfect matching derangement graph. This, with the Delsarte-Hoffman bound, implies that a maximum intersecting set of perfect matchings corresponds to a facet in the perfect matching polytope. The characterization of the maximum set of intersecting perfect matchings follows from the characterization of the facets of this polytope.
Meagher and Moura [8] proved a version of the EKR theorem holds for intersecting uniform partitions using a counting argument [8]. This result includes the EKR theorem for perfect matchings. It is interesting that the counting argument in [8] is straight-forward, except for the case of perfect matchings; in this case a more difficult form of the counting method is necessary.
2 Perfect matchings
A perfect matching is a set of vertex disjoint edges in the complete graph K2k. This is equivalent to a partition of a set of size 2k into k-disjoint classes, each of size 2. The number of perfect matchings in K2k is
With this notation, there are (2k - 1)!! perfect matchings.
We say that two perfect matchings are intersecting if they both contain a common edge. Further, a set of perfect matchings is intersecting if the perfect matchings in the set are pairwise intersecting. If e represents a pair from {1,..., 2k}, then e is an edge of K2k. Define Se to be the set of all perfect matchings that include the edge e. For any edge e, the set Se is intersecting. Any set Se, where e is a pair from {1,..., 2k}, is called a canonically intersecting set of perfect matchings. For every e
The main result of this paper can be stated as follows.
Theorem 2.1. The largest set of intersecting perfect matchings in K2k has size (2k — 3)!!. The only sets that meet this bound are the canonically intersecting sets of perfect matchings.
3 Perfect matching derangement graph
One approach to proving EKR theorems for different objects is to define a graph where the vertices are the objects and two objects are adjacent if and only if they are not intersecting (see [4, 9, 15] for just a few examples of where this is done). This is the approach that we take with the perfect matchings.
We use the standard graph notation. A clique in a graph is a set of vertices in which any two are adjacent; a coclique is a set of vertices in which no two are adjacent. If X is a graph, then w(X) denotes the size of the largest clique, and a(X) is the size of the largest coclique. A graph is vertex transitive if its automorphism group is transitive on the vertices.
For an odd integer n define
n!! = n(n — 2)(n — 4) • • • 1.
|Se| = (2k — 3)!! = (2k — 3)(2k — 5) • • • 1.
C. Godsil andK. Meagher: An algebraic proof of the Erdos-Ko-Rado theorem for intersecting.
207
For a vertex-transitive graph, there is a relationship between the maximum clique size and maximum coclique size known as the clique-coclique bound. The next result is this bound.
Theorem 3.1. Let X be a vertex-transitive graph, then
a(X) w(X) < |V(X)|.	□
The eigenvalues of a graph are the eigenvalues of the adjacency matrix of the graph. Similarly, the eigenvectors and eigenspaces of the graph are the eigenvectors and eigenspaces of the adjacency matrix.
Define the perfect matching derangement graph M(2k) to be the graph whose vertices are all perfect matchings on K2k and vertices are adjacent if and only if they have no common edges. Theorem 2.1 is equivalent to the statement that the size of the maximum coclique in M(2k) is (2k - 3)!! and that only the canonically intersecting sets meet this bound.
The number of vertices in M(2k) is (2k — 1)!!. The degree of M(2k), denoted by d(2k), is the number of perfect matchings that do not contain any the edges from some fixed perfect matching. This number can be calculated using the principle of inclusion-exclusion:
d(2k) = ¿(-l)^k) (2k — 2i —1)!!.	(3.1)
¿=0 W
In practice, this formula can be tricky to use, but we will make use the following simple lower bound on d(2k).
Lemma 3.2. For any k
-1)!!-
d(2k) > (2k - 1)!! - ( i I (2k - 3)!!.
Proof. For any i G {0,..., k — 1}
^ (2k — 2i — 1)!! = i+i (. M (2k — 2i — 1)(2k — 2(i + 1) — 1)!!
i J	k — iyi + 1/
> ^ + J (2k — 2(i +1) — 1)!!
(since 1+4 (2k—2i—1) > 1 for these values of i). This implies that the terms in Equation 3.1 are strictly decreasing in absolute value. Since it is an alternating sequence, the first two terms give a lower bound on d(2k).	□
Next we give some simple properties of the perfect matching derangement graph, including a simple proof of the bound in Theorem 2.1 that uses the clique-coclique bound.
Theorem 3.3. Let M(2k) be the perfect matching derangement graph.
1.	The graph M(2k) is vertex transitive, and Sym(2k) is a subgroup of the automorphism group of M(2k).
2.	The size of a maximum clique in M (2k) is 2k — 1.
208
Ars Math. Contemp. 12 (2017) 383-413
3. The size of a maximum coclique in M (2k) is (2k — 3)!!.
Proof. It is clear that the group Sym(2k) acts transitively on the perfect matchings and, though this action, each permutation in Sym(2k) gives an automorphism of M(2k).
Let C be a clique in M(2k). For every perfect matching in C, the element 1 is matched with a different element of {2, 3,..., 2k}. Thus the size of C is no more than 2k — 1. A 1-factorization of the complete graph on 2k vertices is a clique of size 1(22fc) in M(2k). Since a 1-factorization of K2fc exists for every k, the size of the maximum clique is exactly kk (22fc) = 2k — 1.
Since M(2k) is vertex transitive, the clique-coclique bound, Theorem 3.1, holds so
a(M(2k)) <	=(2k — 3)!!.
k V 2 )
Since the size of any canonically intersecting set meets this bound, we have that
a(M (2k)) = (2k — 3)!!.
□
4 Perfect matching association scheme
We have noted that the group Sym(2k) acts on the set of perfect matchings. Under this action, the stabilizer of a single perfect matching is isomorphic to the wreath product of
Sym(2) and Sym(k). This is a subgroup of Sym(2k) and is denoted by Sym(2) I Sym(k). Thus the set of perfect matchings in K2kk correspond to the set of cosets
Sym(2k)/(Sym(2) \ Sym(k)).
This implies that the action of Sym(2k) on the perfect matchings is equivalent to the action of Sym(2k) on the cosets Sym(2k)/(Sym(2) I Sym(k)). This action produces a permutation representation of Sym(2k). We will not give much detail on the representation theory of the symmetric group, rather we will simply state the results that we need a refer the reader to any standard text on the representation theory of the symmetric group, such as [1, 3, 7, 12].
Each irreducible representation of Sym(2k) corresponds to an integer partition A h 2k; these representations will be written as xa and the character will be denoted by xA. The Sym(2k)-module will be denoted by Va. Information about the representation is contained in the partition. For example, the dimension of the representation can be found just from the partition using the hook length formula.
For any group G, the trivial representation of G is denoted by 1G (and the character by 1G). If X is a representation of a group H < Sym(n), then indSym(n)(x) is the representation of Sym(n) induced by x. Similarly, if x is a representation of Sym(n), then resH (x) is the restriction of x to H. The permutation representation of Sym(2k) acting on Sym(2k)/(Sym(2) I Sym(k)) is the representation induced on Sym(2k) by the trivial representation on Sym(2) I Sym(k) which is denoted by indsym(2fc)(1sym(2);sym(fc)) (see [5, Chapter 13] for more details).
For an integer partition A h k with A = (Ai, A2,..., A^), let 2A denote the partition (2Ai, 2A2,..., 2A^) of 2k. It is well-known (see, for example, [13, Example 2.2]) that
C. Godsil andK. Meagher: An algebraic proof of the Erdos-Ko-Rado theorem for intersecting.
209
decomposition of the permutation representation of Sym(2k) from its action on the perfect matchings is
indSym(2fc)(lsym(2)iSym(fc}) = ^^ X2A '
Ah k
The multiplicity of each irreducible representation in this decomposition is one, this implies that indSym(2k)(1Sym(2);Sym(k)) is a multiplicity-free representation. This implies that the adjacency matrices of the orbitals from the action of Sym(2k) on the cosets Sym(2k)/(Sym(2) I Sym(k)) defines an association scheme on the perfect matchings (see [5, Section 13.4] for more details and a proof of this result). This association scheme is known as the perfect matching scheme. Each class in this scheme is labelled with a partition 2A = (2Ai, 2A2,..., 2A^). Two perfect matchings are adjacent in a class if their union forms a set of I cycles with lengths 2A1, 2A2,..., 2A^ (this association scheme is described in more detail in [5, Section 15.4] and [10]).
The graph M(2k) is the union of all the classes in this association scheme in which the corresponding partition contains no part of size two. This means that each eigenspace of M(2k) is the union of modules of Sym(2k); each module in this union is a Sym(2k)-module V2A where A h k. If £ is an eigenvalue of M (2k), and its eigenspace includes the Sym(2k)-module V2A, then we say that £ is the eigenvalue for V2A. Conversely, we denote the eigenvalue for V2A by £2A.
The next lemma contains a formula to calculate the eigenvalue for the Sym(2k)-module V2A. This gives considerable information about the eigenvalues of M(2k). For a proof the general form of this formula see [5, Section 13.8], we only state the version specific to perfect matchings. If M denotes a perfect matching and a G Sym(2k), we will use Ma to denote the matching formed by the action of a on M.
Lemma 4.1. Let M be a fixed perfect matching in K2k. Let H C Sym(2k) be the set of all elements a G Sym(2k) such that M and Ma are not intersecting. The eigenvalue of M(2k) for the Sym(2k)-module V2A is
d(2k) ^ . .
£2A =	X2A(x).
xeH
The Sym(2k)-module V2A is a subspace of the £2A-eigenspace and the dimension of this subspace is x2A(1).	□
This formula can be used to calculate the eigenvalue corresponding to a module for the matching derangement graph, but it is not effective to determine all the eigenvalues for a general matching derangement graph. In Section 6 we will show another way to find some of the eigenvalues.
5 Delsarte-Hoffman bound
In Section 6, we will give an alternate proof of the bound in Theorem 2.1 that uses the eigenvalues of the matching derangement graph. This proof is based on the Delsarte-Hoffman bound, which is also known as the ratio bound. The advantage of this bound is that when equality holds we get additional information about the cocliques of maximum size. This information can be used to characterize all the sets that meet the bound. The Delsarte-Hoffman bound is well-known and there are many references, we offer [5, Theorem 2.4.1] for a proof.
210
Ars Math. Contemp. 12 (2017) 383-413
Theorem 5.1. Let X be a k-regular graph with v vertices and let t be the least eigenvalue of A(X). Then
v
a(X) <
1 -
T
If equality holds for some coclique S with characteristic vector vs, then
|S| .
vs — MX)1
is an eigenvector with eigenvalue t.	□
If equality holds in the Delsarte-Hoffman bound, we say that the maximum cocliques are ratio tight.
The Delsarte-Hoffman bound can be used to prove the EKR theorem for sets. Similar to the situation for the perfect matchings, the group Sym(n) acts on the subsets of {1,..., n} of size k. This action is equivalent to the action of Sym(n) on the cosets Sym(n)/(Sym(n-k) x Sym(k)). This action corresponds to a permutation representation, namely
k
indsym(n) (1Sym(n-
¿=0
(Details can be found in any standard text on the representation theory of the symmetric group.) This representation is multiplicity free and the orbital schemes from this action is an association scheme better known as the Johnson scheme.
The Kneser graph K(n, k) is the graph whose vertices are all the k-sets from {1,..., n} and two vertices are adjacent if and only if they are disjoint. The Kneser graph is a graph in the Johnson scheme, it is the graph that corresponds to the orbitals of pairs of sets that do not intersect. A coclique in K(n, k) is a set of intersecting k-sets. The Kneser graph is very well-studied and all of its eigenvalues are known (see [6, Chapter 7] or [5, Section 6.6] for a proof).
Proposition 5.2. The eigenvalues of K(n, k) are
-,Yfn — k — i (-1)
with multiplicities (") — (¿^J for i G {0,..., k}.	□
If we apply the Delsarte-Hoffman bound to K(n, k) we get the following theorem which is equivalent to the standard EKR theorem. The characterization follows from the second statement in the Delsarte-Hoffman bound, see [5, Section 6.6] for details.
Theorem 5.3. Assume that n > 2k. The size of the largest coclique in K(n, k) is (k-i), and the only cocliques of this size consist of all k-sets that contain a common fixed element.	□
To apply the Delsarte-Hoffman bound to M(2k), we first need to determine the value of the least eigenvalue of M(2k). We do not calculate all the eigenvalues of M(2k), rather we calculate the two eigenvalues with the largest absolute value and then show that all other eigenvalues have smaller absolute value.
C. Godsil andK. Meagher: An algebraic proof of the Erdos-Ko-Rado theorem for intersecting.
211
6 Eigenvalues of the matching derangement graph
In this section we determine the largest and the least eigenvalue of the matching derangement graph. Further, we identify the modules that the eigenvalues are for. First we will use a simple method to show that these two values are eigenvalues of M(2k).
For any edge e in K2k, the partition n = {Se, V(M(2k))/Se} is an equitable partition of the vertices in M(2k). In fact, n is the orbit partition formed by the stabilizer of the edge e in Sym(2k) (this subgroup is isomorphic to Sym(2) x Sym(2k - 2)) acting on the set of all vertices of M(2k). Each vertex in Se is adjacent to no other vertices in Se (since it is a coclique), and is adjacent to exactly d(2k) vertices in V(M(2k))/Se. A straight-forward counting argument shows that each vertex in V(M(2k))/Se is adjacent to exactly d(2k)/(2k - 2) vertices in Se, and thus to d(2k) - d(2k)/(2k - 2) other vertices in V(M(2k))/Se. This implies that the quotient graph of M(2k) with respect to the partition n is
0 d(2k)
M(2k)/n =[ 2k- d(2k) 2k-3 d(2k)
The eigenvalues for the quotient graph M(2k)/n are
d(2k)
d(2k),

2k 2
Since n is equitable, these are also eigenvalues of M(2k). The next result identifies the modules which the eigenvalues are for.
Lemma 6.1. The eigenvalue of M(2k) for the Sym(2k)-module V[2k] is d(2k), and the eigenvalue of M(2k) for the Sym(2k)-module V[2k_2i2] is -d(2k)/(2k - 2).
Proof. The first statement is clear using the formula in Lemma 4.1.
To prove the second statement, we will consider the equitable partition n defined above. The partition n is the orbit partition of Sym(2) x Sym(2k - 2) acting on the perfect match-ings. Let H = Sym(2) x Sym(2k - 2) and denote the cosets of H in Sym(2k) by {xoH = H, xiH,..., x2fc2_fc_1H}.
The -d(2k)/(2k - 2)-eigenvector of M(2k)/n lifts to an eigenvector v of M(2k). A simple calculation shows that the entries of v are 1 - or - 2f~i, depending on if the index of the entry is in Se, or not. This means that v = ve - 2nii 1, where ve is the characteristic vector of Se.
The group Sym(2k) acts on the edges of K2k, and for each a e Sym(2k), we can define
1
e 2k - 1
Under this action, the vector v is fixed by any permutation in H. If we define
V = span{vCT : a e Sym(2k)},
then V is a subspace of the -d(2k)/(2k - 2)-eigenspace. Moreover, V is invariant under the action of Sym(2k), so it is also a Sym(2k)-module. To prove this lemma we need to show that V is isomorphic to the Sym(2k)-module Vpfc_2j2j.
Let W be the Sym(2k)-module for the induced representation indSym(2k)(1H). By Equation 5.1, W is the sum of irreducible modules of Sym(2k) that are isomorphic to
212
Ars Math. Contemp. 12 (2017) 383-413
M[2fc], M[2fc_i,i] and M[2k_2,2]. The vector space W is isomorphic to the vector space of functions f G L(Sym(2k)) that are constant on H. For each coset xH, let SxH(a) be the characteristic function for xH; so SxH (a) is defined to be equal to 1 if a is in xH, and 0 otherwise. Since W is the Sym(2k)-module for the representation induced by 1H, the functions SxH form a basis for W (see [5, Section 11.13] for details). Define the map f : V ^ W so that
1 2k2_k_1
f K) = SaH —	Y, SXiH.
¿=0
Since va = vn if and only if aH = nH, this function is well-defined. Further, it is a Sym(2k)-module homomorphism. Thus V is isomorphic to a submodule of W. Since V is not trivial, it must be the Sym(2k)-module V[2k_2,2], since it is the only module (other than the trivial) that is common to both indsym(2k)(lH) and indsym(2k)(1sym(2)isym(k}). □
We have found two of the eigenvalues of M(2k), next we will show that all the remaining eigenvalues are smaller in absolute value. We need the following theorem by Rasala [11] that gives bounds on the dimension of the irreducible representations of
Sym(n).
Theorem 6.2. For n > 15, the irreducible representations with the seven smallest degrees are given in the following table.
Representations	Degree
[n], [1n] [n — 1, 1], [2,1n_2] [n — 2, 2], [2, 2,1n_4] [n — 2, 1,1], [3,1n_3] [n — 3, 3], [2, 2, 2,1n_6] [n — 3,1,1,1], [4,1n_4] [n — 3, 2,1], [3, 2,1n_5]	1 n — 1 2 n(n — 3) 2	(n — 1)(n — 2) 6 n(n — 1)(n — 5) 1 (n — 1)(n — 2)(n — 3) 3	n(n — 2)(n — 4)
Next we will bound the size of the other eigenvalues. This bound follows from the straightforward fact that if A is the adjacency matrix of a graph, then the trace of the square of A is equal to both the sum of the squares of the eigenvalues of A, and to twice the number of edges in the graph. The proof of this result closely follows the proof of the least eigenvalue of the derangement graph of the symmetric group by Ellis [2].
Theorem 6.3. For A h k, the absolute value of the eigenvalue of M (2k) for the Sym(2k)-module V2A is strictly less than d(2k)/(2k — 2), unless A = [k] or A = [k — 1,1].
Proof. If 2k < 15, this theorem can be checked by directly calculating all the eigenvalues (this can easily be done using a computational algebra program such as GAP [16]), so we will assume that 2k > 16.
Let A be the adjacency matrix of M(2k) and use £2A to denote the eigenvalue for the Sym(2k)-module V2A. The sum of the eigenvalues of A2 is twice the number of edges in M(2k), that is
E X2A(1)& = (2k — 1)!! d(2k).
Ah k
C. Godsil andK. Meagher: An algebraic proof of the Erdos-Ko-Rado theorem for intersecting.
213
From Lemma 6.1 we know the eigenvalues for two of the modules, so this bound can be expressed as
E X2a(1)£22a = (2k-1)!! d(2k) - d(2k)2 - (2k2-3k) (f®) ' .
Ahfc	^	'
A=[fc],[fc-1,1]
Since all the terms in left-hand side of the above summation are positive, any single term is less than the sum. Thus
X2A(1)& < (2k-1)!! d(2k) - d(2k)2 - (2k2-3k)	2 ,
(where A h k and A = [k], [k - 1,1]). If |^a| > d(2k)/(2k - 2), then this reduces to
(2k - l)!!(2k - 2)2 ,2 XA(1) < (-^y—^ - 6k2 + llk - 4.
Using the bound in Lemma 3.2, this implies that
Xa(1) < 2*2 - k = Mlz(M.
If |C2a | > d(2k)/(2k - 2), then 2A must be one of the first four representations in the table of Theorem 6.2. Thus 2A must be either [2k] or [2k - 2,2], which proves the result. □
We restate this result in terms of the least eigenvalue of the matching derangement graph; noting that Theorem 6.3 implies that V[2k-2,2] is the only Sym(2k)-module that has -d(2k)/(2k - 2) as its eigenvalue.
Corollary 6.4. The smallest eigenvalue of M(2k) is -d(2k)/(2k - 2) and the multiplicity of this eigenvalue is 2k2 - 3k.	□
7 The Sym(2k)-module V[2k-2,2]
Applying the Delsarte-Hoffman bound with the fact that -d(2k)/(2k - 2) is the least eigenvalue of M(2k), proves that any canonical coclique is ratio tight since
|V(M(2k))| (2k - l)!!
l _ d	1 d(2fc)
1 T	1 - _ d(2k)
2k-2
= (2k - 3)!!.
For S a maximum coclique in M(2k) we will use vS to denote the characteristic vector of S. The ratio bound implies that |S| = (2k - 3)!! and, further, that
l ^
s 2k - l
is a -d(2k)/(2k - 2)-eigenvector. This vector is called the balanced characteristic vector of S, since is it orthogonal to the all ones vector. Since the Sym(2k)-module V[2k-2,2] is the only module for which the corresponding eigenvalue is the least (this follows directly from Theorem 6.3) we have the following result which will be used to determine the structure of the maximum cocliques in M (2k).
Lemma 7.1. The characteristic vector for any maximum coclique in M (2k) is in the direct sum of the Sym(2k)-modules V^2fc] and V[2k-2,2].	□
214
Ars Math. Contemp. 12 (2017) 383-413
A perfect matching is a subset of the edges in the complete graph, and thus can be represented as a characteristic vector; this is a vector in R( 2). Define the incidence matrix for the perfect matchings in K2k to be the matrix U whose rows are the characteristic vectors of the perfect matchings of K2k. The columns of U are indexed by the edges in the complete graph and the rows are indexed by the perfect matchings. The column of U corresponding to the edge e is the characteristic vector of Se.
We will show that the characteristic vector of any maximum coclique of M(2k) is a linear combination of the columns of U.
Lemma 7.2. The characteristic vectors of the canonical cocliques of M(2k) span the direct sum of the Sym(2k)-modules V[2k] and V[2k_2,2].
Proof. Let ve be the characteristic vector of Se. From Lemma 7.1, the vector ve — 2k~l 1 is in the Sym(2k)-module V[2k_2,2], and ve is in the direct sum of the Sym(2k)-modules V^2k] and V^2k_2 2]. So all that needs to be shown is that the span of all the vectors ve has dimension 2k2 — 3k + 1, or equivalently, that the rank of U is 2k2 — 3k + 1.
Let / denote the (2) x (2) identity matrix and A(2k, 2) the adjacency matrix of the Kneser graph K(2k, 2). Then
UTU = (2k — 3)!!/ + (2k — 5)!!A(2k, 2).
By Proposition 5.2, 0 is an eigenvalue of this matrix with multiplicity 2k — 1. Thus the
2k1 2
rank of UTU (and hence U) is (22k) — (2k — 1) = 2k2 — 3k +1.	□
This result, and the comments at the beginning of this section, imply the following corollary.
Corollary 7.3. The characteristic vector of a maximum coclique in the perfect matching derangement graph is in the column space of U.	□
Next we will show that this implies that any maximum coclique is a canonical intersecting set. To do this we will consider a polytope based on the perfect matchings.
8 The perfect matching polytope
The convex hull of the set of characteristic vectors for all the perfect matchings of a graph K2k is called the perfect matching polytope of K2k. Let U be the incidence matrix defined in the previous section, then the perfect matching polytope is the convex hull of the rows of U. A face of the perfect matching polytope is the convex hull of the rows where Uh achieves its maximum for some vector h. A facet is a maximal proper face of a polytope.
If S is a maximum coclique in M(2k), then from Corollary 7.3, we know that Uh = vs for some vector h. If a vertex of K2k is in S, then the corresponding row of Uh is equal to 1; conversely, if a vertex of K2k is not in S, then the corresponding row of Uh is equal to 0. Thus a maximum intersecting set of perfect matchings is a facet of the perfect matching polytope. In this section, we will give a characterization of the facets of the perfect matching polytope for the complete graph.
Let S be a subset of the vertices of K2k and define the boundary of S to be the set of edges that join a vertex in S to a vertex not in S. The boundary is denoted by dS and is also known as an edge cut. If S is a subset of the vertices of K2k of odd size, then any
C. Godsil andK. Meagher: An algebraic proof of the Erdos-Ko-Rado theorem for intersecting.
215
perfect matching in K2k must contain at least one edge from dS. If S is a single vertex, then any perfect matching contains exactly one element of dS. It is an amazing classical result of Edmonds that these two constraints characterize the perfect matching polytope for any graph. For a proof of this result see Schrijver [14].
Theorem 8.1. Let X be a graph. A vector x in R|E(X)| lies in the perfect matching polytope of X if and only if:
(a)	x > 0;
(b)	if S = {u} for some u G V(X), thenYe£ds x(e) = 1
(c)	if S is an odd subset of V(X) with |S| > 3, then YeedS x(e) > 1.
If X is bipartite, then x lies in the perfect matching polytope if and only if the first two conditions hold.	□
The constraints in Equation (b) define an affine subspace of R|E(X)|. The perfect matching polytope is the intersection of this subspace with affine half-spaces defined by the conditions in Equation (a) and Equation (c); hence the points in a proper face of the polytope must satisfy at least one of these conditions with equality.
For any graph X (that is not bipartite) the vertices of a facet are either the perfect matchings that miss a given edge, or the perfect matchings that contain exactly one edge from dS for some odd subset S.
It follows from Theorem 8.1 that every perfect matching in K2k is a vertex in the perfect matching polytope for the complete graph. But we can also determine the vertices of every facet in this polytope.
Lemma 8.2. In the matching polytope of K2k, the vertices of a facet of maximum size are the perfect matchings that do not contain a given edge.
Proof. Let F be a facet of the polytope of maximum size. From the above comments, equality holds in at least one of equations
E x(e) > 1
eess
for all x g F. Suppose S is the subset that defines such an equation, then S is an odd subset of the vertices in K2k for which J2e£ds x(e) = 1 for all x G F.
Let s be the size of S. Each perfect matching with exactly one edge in dS consists of the following: a matching of size (s - 1)/2 covering all but one vertex of S; an edge joining this missed vertex of S to a vertex in S; and a matching of size (2k - s - 1)/2 covering all but one vertex in S. Hence there are
(s - 2)!! s(2k - s) (2k - s - 2)!! = s!!(2k - s)!!
such perfect matchings. We denote this number by N(s) and observe that
N(s - 2) _ 2k - s + 2 N (s) = s '
217
Ars Math. Contemp. 12 (2017) 383-413
Hence for all s such that 3 < s < k we see that the values N(s) are strictly decreasing, so the maximum size of a set of such vertices is N(3) = 3(2k - 3)!!.
On the other hand, the number of perfect matchings in K2k that do not contain a given
edge is
(2k - 1)!! - (2k - 3)!! = (2k - 2)(2k - 3)!!.
Since this is always larger than N(3), the lemma follows.	□
We now have all the tools to show that any maximum intersecting set of perfect matchings is the set of all matchings that contain a fixed edge.
Theorem 8.3. The largest coclique in M(2k) has size (2k - 3)!!. The only cocliques that meet this bound are the canonically intersecting sets of perfect matchings.
Proof. Let S be a maximum coclique in M(2k) and let vS be the characteristic vector of S. Then |S| = (2k - 3)!!, by the Delsarte-Hoffman bound and Corollary 6.4. TheDelsarte-Hoffman bound, along with Theorem 6.3, further imply that the vector vS - 1 is in the Sym(2k)-module Vj2fc_2,2].
By Lemma 7.2, vS - ^jh 1 is a linear combination of the balanced characteristic vectors of the canonical cocliques. This also implies that vS is a linear combination of the characteristic vectors of the canonical cocliques. So there exists a vector x such that Ux = vS (where U is the matrix defined in Section 7).
Finally, by Lemma 8.2, S is a face of maximal size an it consists of all the perfect matching that avoid a fixed edge. This implies that S is a canonical coclique of M (2k). □
References
[1]	T. Ceccherini-Silberstein, F. Scarabotti and F. Tolli, Representation Theory of the Symmetric Groups, volume 121 of Cambridge Studies in Advanced Mathematics, Cambridge University Press, Cambridge, 2010, doi:10.1017/cbo9781139192361.
[2]	D. Ellis, A proof of the Cameron-Ku conjecture, J. Lond. Math. Soc. (2) 85 (2012), 165-190, doi:10.1112/jlms/jdr035.
[3]	W. Fulton and J. Harris, Representation Theory, Graduate Texts in Mathematics, SpringerVerlag, New York, 1991, doi:10.1007/978-1-4612-0979-9.
[4]	C. Godsil and K. Meagher, A new proof of the Erdos-Ko-Rado theorem for intersecting families of permutations, European J. Combin. 30 (2009), 404-414, doi:10.1016/j.ejc.2008.05.006.
[5]	C. Godsil and K. Meagher, Erdos-Ko-Rado Theorems: Algebraic Approaches, Cambridge Studies in Advanced Mathematics, Cambridge University Press, Cambridge, 2015, doi: 10.1017/cbo9781316414958.
[6]	C. Godsil and G. Royle, Algebraic Graph Theory, volume 207 of Graduate Texts in Mathematics, Springer-Verlag, New York, 2001, doi:10.1007/978-1-4613-0163-9.
[7]	G. James and A. Kerber, The Representation Theory of the Symmetric Group, volume 16 of Encyclopedia ofMathematics and its Applications, Addison-Wesley Publishing Co., Reading, Massachusetts, 1981.
[8]	K. Meagher and L. Moura, Erdos-Ko-Rado theorems for uniform set-partition systems, Electron. J. Combin. 12 (2005), R40.
[9]	K. Meagher and P. Spiga, An Erdos-Ko-Rado theorem for the derangement graph of PGL(2, q) acting on the projective line, J. Combin. Theory Ser. A 118 (2011), 532-544, doi:10.1016/j.jcta. 2010.11.003.
C. Godsil andK. Meagher: An algebraic proof of the Erdos-Ko-Rado theorem for intersecting.
44
[10]	M. Muzychuk, On association schemes of the symmetric group S2n acting on partitions of type 2n, Bayreuth. Math. Schr. 47 (1994), 151-164.
[11]	R. Rasala, On the minimal degrees of characters of Sn, J. Algebra 45 (1977), 132-181.
[12]	B. E. Sagan, The Symmetric Group, The Wadsworth & Brooks/Cole Mathematics Series, Wadsworth & Brooks/Cole Advanced Books & Software, Pacific Grove, California, 1991.
[13]	J. Saxl, On multiplicity-free permutation representations, in: Finite Geometries and Designs, Cambridge Univ. Press, Cambridge, volume 49 of London Math. Soc. Lecture Note Ser., pp. 337-353, 1981.
[14]	A. Schrijver, Short proofs on the matching polyhedron, J. Combin. Theory Ser. B 34 (1983), 104-108, doi:10.1016/0095-8956(83)90066-7.
[15]	H. Tanaka, Classification of subsets with minimal width and dual width in Grassmann, bilinear forms and dual polar graphs, J. Combin. Theory Ser. A 113 (2006), 903-910, doi:10.1016/j.jcta. 2005.08.006.
[16]	The GAP Group, GAP - Groups, Algorithms, and Programming, Version 4.7.7, 2015.