A new proof of the Erd\H{o}s-Ko-Rado theorem for intersecting families of permutations

• The paper gives a substantially different proof of Cameron and Ku’s theorem for intersecting permutations.The classical Erdős-Ko-Rado theorem concerns intersecting k-subsets and identifies the families attaining its bound [7].Source: §1 · pp. 1–2
• For permutations, two permutations are intersecting when they agree at some point, and the natural extremal families are the cosets of a point stabiliser.These families have the form S_i,j = {π ∈ S(n) : π(i) = j}.Source: §1 · p. 2
• Cameron and Ku state that, for n ≥ 2, an intersecting family S of permutations with |S| = (n − 1)! is a coset of a stabiliser of a point.Source: §1 · p. 2
• Cameron and Ku’s proof uses fixing to show that the fixed-point sets of a maximum family form an intersecting set system, whose members share a common point [4].Their argument assumes the family contains the identity permutation.Source: §1 · pp. 2–3
• The alternate proof uses the permutation graph together with association-scheme properties and information about symmetric-group representations.Source: §1 · p. 3
• The authors note that this approach has also been used for sets and other objects, and suggest generalizing it further.Source: §1 · pp. 2–3
• The proof applies only for n > 6; the smaller cases can be verified using GAP.Source: §1 · p. 3

• The section gives a new proof of this bound, which was originally proved by Delsarte.Cameron and Ku also gave an alternate proof for vertex-transitive graphs.Source: §2 · p. 3
• For a clique C and independent set S in a union of association-scheme graphs, the bound is |C||S| ≤ v.Here v is the number of vertices.Source: §2 · pp. 3–4
• When equality holds, x^T E_j x · y^T E_j y = 0 for every j > 0, where x and y are the characteristic vectors of C and S.The E_j are the association scheme’s principal matrix idempotents.Source: §2 · pp. 3–4
• If the clique–coclique bound holds with equality for maximum C and S, then for each j > 0 at most one of E_j x and E_j y is nonzero.Source: §2 · p. 4

• P(n) has permutations as vertices, with two adjacent exactly when they disagree at every point; it is a normal Cayley graph whose connection set is the derangements.Source: §3 · p. 5
• P(n) is a union of graphs in the conjugacy-class association scheme, so the clique–coclique bound applies.The paper notes that the bound yields the size statement and that this bound was previously shown by Deza and Frankl and Cameron and Ku [4].Source: §3 · pp. 5–6
• The maximum clique in P(n) has size n, attained by the rows of a Latin square of order n.A clique has at most n vertices because the image of any fixed point must differ across its permutations; a Latin square exists for every n.Source: §3 · p. 6
• A maximum independent set in P(n) has size (n − 1)!, and the sets S_i,j attain this bound.Intersecting families are exactly the independent sets in P(n).Source: §3 · pp. 5–6

4.1 Lemma. For all positive integers n

• The partition {S_n,n, V(P(n) S_n,n)} is equitable, and its quotient-graph eigenvalues are also eigenvalues of P(n).The partition is the orbit partition under S(1)S(n1).Source: §4.1 · p. 7
• For a d(n)-regular graph, the largest eigenvalue of P(n) is d(n), and the least eigenvalue gives a bound on the maximum independent-set size via the ratio bound.The section notes that Ku conjectured the least eigenvalue of P(n) is −d(n).Source: §4.1 · p. 7
• Eigenvalues of P(n) are obtained by summing conjugacy-class eigenvalues over the classes of derangements.The conjugacy-class eigenvalues are determined using the character table of the symmetric group.Source: §4.1 · pp. 7–8

5 The (n −1)-module

• The proof's final step shows that a maximum independent-set characteristic vector in the span of these basis vectors must be one of the v_i,j.Here v_i,j denotes the characteristic vector of S_i,j.Source: §5 · pp. 8–9
• For n > 6, every maximum independent set S has v_S − (1/n)1 in the [n − 1, 1]-module.The proof uses maximum cliques with nonzero character sums to eliminate the other modules.Source: §5 · p. 9
• For n > 6, a clique built from a decomposition of the complete digraph into directed cycles supplies character sums used to distinguish the [n − 1, 1]-module.For odd n, the proof instead constructs a clique from rows of a Latin square to rule out the conjugate partition [2, 1^(n−2)].Source: §5 · pp. 9–10
• The vectors v_i,j − (1/n)1 for i,j < n form a basis for the [n − 1, 1]-module.The proof establishes their linear independence using a matrix whose entries record whether π(i) = j.Source: §5 · p. 10

Proof of Theorem 1.2

• H records whether each permutation maps i to j, while N, M, and W select derangement rows, off-diagonal columns, and diagonal columns, respectively.Source: §6 · p. 11
• The characteristic vector of any maximum independent set lies in the span of the columns of H together with the all-ones vector.Source: §6 · p. 11
• For all n, M has rank (n −1)(n −2); the proof exhibits a submatrix equal to K_n−1 ⊗ I_n−2.The submatrix is formed using the ordered permutations π_a,b described in the proof.Source: §6 · pp. 11–12
• If y lies in the kernel of N, then Hy lies in W’s column space because M’s full rank forces the corresponding entries of y to vanish.Source: §6 · p. 12
• Assuming the identity is in S, the two cases show any maximum independent set is S_i,i for some i in {1, ..., n}.For i<n the proof obtains S_i,i; the other case gives S_n,n.Source: §6 · pp. 13, 15
• When vS lies in H’s column space, its representation in W has at most one nonzero coefficient, so S is S_i,i for some i<n.Two simultaneous nonzero coefficients would make a coordinate of the characteristic vector equal to 2.Source: §6 · p. 13
• When vS is outside H’s column space, the augmented representation [H|1]y yields the remaining case, S_n,n.Source: §6 · pp. 14–15

Further Work

• Deza and Frankl conjectured that, for sufficiently large n, the maximum size of a t-intersecting permutation family is (n −t)!.Source: §7 · pp. 15–16
• Cameron and Ku note that their method cannot be extended to t-intersecting permutations, motivating the proposed alternative extension.Source: §7 · p. 16
• The authors conjecture that a shifted maximum independent-set vector in P_1(n), corresponding to a 2-intersecting permutation family, lies in modules of depth at most 2.The listed modules are [n], [n −1, 1], [n −2, 2], and [n −2, 1, 1].Source: §7 · p. 16
• For n = 4, 5, 6, the dimensions of the proposed module sum and the span of the specified shifted vectors agree.The vectors are indexed by A = {(i, j), (k, ℓ)}.Source: §7 · p. 16
• The authors propose extending the module conjecture to maximum independent sets in P_t(n), with shifted vectors supported on modules of depth at most t.Source: §7 · p. 16
• The authors suggest applying this method to perfect matchings and uniform partitions as steps toward a more general theory of Erdős-Ko-Rado theorems.Source: §7 · pp. 16–17