2018. 11. 22. 12:15 - 2018. 11. 22. 13:45
MTA Rényi Intézet, nagyterem
-
-
-
-
Esemény típusa: szeminárium
Szervezés: Intézeti
-
Extremális halmazrendszerek szeminárium

Leírás

A perfect matching of a complete graph $K_{2n}$ is a 1-regular subgraph that contains all the vertices.

Two perfect matchings intersect if they share an edge. It is known that if $\mathcal{F}$ is family of

intersecting perfect matchings of $K_{2n}$, then $|\mathcal{F}| \leq (2(n-1) - 1)!!$ and if equality holds,

then $\mathcal{F} = \mathcal{F}_{ij}$ where $ \mathcal{F}_{ij}$ is the family of all perfect matchings of

$K_{2n}$ that contain some fixed edge $ij$. We give a short algebraic proof of this result, resolving a

question of Godsil and Meagher. Along the way, we show that if a family $\mathcal{F}$ is non-Hamiltonian,

that is, $m \cup m' \not \cong C_{2n}$ for any $m,m' \in \mathcal{F}$, then $|\mathcal{F}| \leq (2(n-1) - 1)!!$

and this bound is met with equality if and only if $\mathcal{F} = \mathcal{F}_{ij}$. Our results make

ample use of a somewhat understudied symmetric commutative association scheme arising from the

Gelfand pair $(S_{2n},S_2 \wr S_n)$. We give an exposition of a few new interesting objects that live

in this scheme as they pertain to our results.