University COVID-19 update

The University of Waterloo is constantly updating our most Frequently Asked Questions.

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 ShiraziExport this event to calendar

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

S M T W T F S
25
26
27
28
29
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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)