pith. sign in

arxiv: 1303.4061 · v1 · pith:AONLKCT3new · submitted 2013-03-17 · 🧮 math.CO · cs.DM

An ErdH{o}s--Ko--Rado theorem for matchings in the complete graph

classification 🧮 math.CO cs.DM
keywords familymatchingsprovetheoremanalogcompleteedgegraph
0
0 comments X
read the original abstract

We consider the following higher-order analog of the Erd\H{o}s--Ko--Rado theorem. For positive integers r and n with r<= n, let M^r_n be the family of all matchings of size r in the complete graph K_{2n}. For any edge e in E(K_{2n}), the family M^r_n(e), which consists of all sets in M^r_n containing e, is called the star centered at e. We prove that if r<n and A is an intersecting family of matchings in M^r_n, then |A|<=|M^r_n(e)|$, where e is an edge in E(K_{2n}). We also prove that equality holds if and only if A is a star. The main technique we use to prove the theorem is an analog of Katona's elegant cycle method.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.