Intersecting families of permutations and set partitions

22 May 2015 NUS mathematicians have recently extended some classical theorems for finite sets in Extremal Combinatorics to other combinatorial structures.

Extremal Combinatorics studies the problem of finding the maximum or minimum size of a collection of discrete configurations that must satisfy certain restrictions. Such problems are often related to areas in Computer Science and Coding Theory. A collection of k-sets of an n-set is said to be t-intersecting if any two of its members have at least t elements in common. One such collection for (n,k,t)=(7,3,1) is the Fano plane (see Figure) where the sets are given by the six lines and the circle: {1,2,3}, {3,4,5}, {1,6,5}, {2,7,5}, {3,7,6}, {1,7,4}, {2,4,6}. This collection has cardinality 7 and it is not the largest 1-intersecting family for the chosen parameters. It turns out that the largest such collection can be constructed, naturally enough, by taking all the 3-sets containing a fixed element say 1: {1,2,3}, {1,2,4}, {1,2,5}, {1,2,6}, {1,2,7}, {1,3,4}, {1,3,5}, {1,3,6}, {1,3,7}, {1,4,5}, {1,4,6}, {1,4,7}, {1,5,6}, {1,5,7}, {1,6,7}. The fact that this is always the case for n sufficiently large in terms of k and t is one of the most fundamental theorems in Extremal Combinatorics known as the Erdos-Ko-Rado Theorem.

The figure shows the Fano plane where the sets are given by the six lines and the circle: {1,2,3}, {3,4,5}, {1,6,5}, {2,7,5}, {3,7,6}, {1,7,4}, {2,4,6}.

The analogous problem for permutations was initiated by Deza and Frankl [1] in 1977 who also conjectured that similar results hold for permutations. This conjecture was settled in the affirmative by Ellis, et al. [2] in 2008, using spectral methods and representations of the symmetric group. One of the main object in this study is the Cayley graph on the symmetric group generated by permutations with certain fixed points. In view of the importance of the eigenvalues of these graphs, a team led by Dr KU Cheng Yeaw from the Department of Mathematics in NUS has successfully derived a recurrence formula for these eigenvalues in terms of the characters of the symmetric group [4], building on their previous work on the derangement graph [8]. They have also recently proved some extensions of the Erdos-Ko-Rado theorem for weak compositions [6] and permutations with fixed number of cycles [7].

Another line of investigation that they have been focusing on is the intersection property for a collection of set partitions, see [5,9]. Among other results, they have proved the analogue of the Hilton-Milner theorem for set partitions, which can be regarded as a strengthening of the Erdos-Ko-Rado theorem. The novelty of their approach is the application of the splitting operation on set partitions in compressing intersecting systems while preserving their sizes and intersecting property.

The study of intersecting families of permutations is closely related to that of codes. In fact, the underlying metric is the Hamming distance for permutations. This has recently attracted researchers in coding theory to study the applications of permutations and their generalizations as codes in powerline communications, see [3] and the references therein.

References

1. Deza M, Frankl, P. “On the maximum number of permutations with given maximal or minimal distance.” J Combin. Theory Ser A 22 (1977) 352.

2. Ellis D, Friedgut E, Pilpel H. “Intersecting families of permutations.” Journal of the American Society 24 (2011) 649.

3. Keevash P, Ku CY “A random construction for permutation codes and the covering radius”Des. Codes. Crypt., 41 (2006) 79.

4. Ku CY, Lau T, Wong KB. “Cayley graphs on symmetric group generated by elements fixing k points” Linear Algebra and Its Applications 471 (2015) 405.

5. Ku CY, Wong KB. “A Deza-Frankl type theorem for set partitions.” The Electronic Journal of Combinatorics, 22 (2015) 1.84.

6. Ku CY, Wong KB B. “On r-cross t-intersecting families of weak compositions.” Discrete Mathematics 338 (2015) 1090.

7. Ku CY, Wong KB. “An Erdos-Ko-Rado Theorem for permutations with fixed number of cycles” The Electronic Journal of Combinatorics 21 (2014) 3.16.

8. Ku CY, Wong KB B. “Solving the Ku-Wales conjecture on the eigenvalues of the derangement graph” European Journal of Combinatorics34 Issue 6 (2013) 941.

9. Ku CY, Wong KB. “An analogue of Hilton-Milner theorem for set partitions”Journal of Combinatorial Theory Series A120 (2013) 1508.