Algebraic Graph Theory Seminar - Andriaherimanana Sarobidy Razafimahatratra & Mahsa Nasrollahi Shirazi

Title: Extensions of the Erdős-Ko-Rado theorem to 2-intersecting perfect matchings and 2-intersecting permutations

Abstract:

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\geq 2k$, then any intersecting family F of k-subsets of [n] = {1,2,...,n} has size at most $\binom{n-1}{k-1}$. Moreover, if n>2k, then equality holds if and only if F is a canonical intersecting family; that is, $\bigcap_{A\in F}A = \{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)\times (2k-7) \times \ldots 3\times 1$, for any $k\geq 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\geq 5$.