Algebraic Graph Theory: Extensions of EKR to 2-intersecting perfect matchings and permutations

Talk by Andriaherimanana Sarobidy Razafimahatratra & Mahsa Nasrollahi Shirazi.

The Erdős-Ko-Rado (EKR) theorem is a classical result in extremal combinatorics. It states that if n and k are such that $n$ is at least 2, then any intersecting family F of k-subsets of [n]={1,2,...,n} has size at most n-1 choose k-1. Moreover, if n is strictly greater than 2k, then equality holds if and only if F is a canonical intersecting family; that is, the intersection over all A in F is {i}, for some i in [n].

The EKR theorem can be extended to various combinatorial objects. In this presentation, we will talk about some variations of the EKR theorem for 2-intersecting perfect matchings and 2-intersecting permutations. In particular, we will first prove that any 2-intersecting family of perfect matchings of K_{2k} has size at most (2k-5)(2k-7)...(3)(1), for any k at least 3. Then, we will show that any 2-pointwise (resp. 2-setwise) intersecting family of Sym(n) has size at most (n-2)! (resp. 2(n-2)!) for n at least 5.

[ab.roberts]

Proud of my tutor, Dr. Shirazi.
From UoM