Given once, 2013

An Erdős–Ko–Rado Theorem for Matchings

Why the largest intersecting family of matchings is a star, via Katona's cycle method

Combinatorics

An intermediate research talk, for graduate students and up.

Abstract

Draft, not yet checked by me

The Erdős–Ko–Rado theorem says that if r ≤ n/2, any family of r-subsets of an n-element set in which every two members share at least one element is no bigger than a star (all r-subsets containing one fixed element). I ask the same question for matchings with r edges in K2n, where two matchings intersect if they have an edge in common. For r < n, an intersecting family is never larger than the star of all r-matchings through a fixed edge, and only stars reach that bound. The proof adapts Katona's cycle method, building its cyclic orders from partitions of the edges of K2n into perfect matchings.

The slides

As a PDF

The viewer needs JavaScript; the PDF below works without it.

Where I have given it

All appearances