## University COVID-19 update

### Questions about buildings and services? Visit the list of Modified Services.

Please note: The University of Waterloo is closed for all events until further notice.

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

Monday, September 14, 2020 — 11:30 AM EDT

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

 Speakers: Andriaherimanana Sarobidy Razafimahatratra & Mahsa Nasrollahi Shirazi Affiliation: University of Regina Zoom: Contact Soffia Arnadottir

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$.

### May 2021

S M T W T F S
25
26
27
28
29
30
1
2
3
4
5
6
7
8
9
11
12
13
15
16
18
19
22
23
24
25
26
27
28
29
30
31
1
2
3
4
5
1. 2021 (45)
1. May (5)
2. April (9)
3. March (13)
4. February (8)
5. January (10)
2. 2020 (119)
1. December (5)
2. November (12)
3. October (12)
4. September (12)
5. August (11)
6. July (17)
7. June (11)
8. May (6)
9. March (11)
10. February (11)
11. January (11)
3. 2019 (167)
4. 2018 (136)
5. 2017 (103)
6. 2016 (137)
7. 2015 (136)
8. 2014 (88)
9. 2013 (48)
10. 2012 (39)
11. 2011 (36)
12. 2010 (40)
13. 2009 (40)
14. 2008 (39)
15. 2007 (15)