Erdős-Ko-Rado for perfect matchings

DOI10.1016/J.EJC.2017.05.005zbMATH Open1369.05173arXiv1409.2057OpenAlexW2730819323MaRDI QIDQ2400976FDOQ2400976

Authors: Nathan Lindzey 

Publication date: 31 August 2017

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Abstract: 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 $mathcalF$ is family of intersecting perfect matchings of $K_{2n}$, then $|mathcalF|leq(2(n-1)-1)!!$ and if equality holds, then $mathcalF=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 $mathcalF$ is non-Hamiltonian, that is, $mcup{m}^{\prime }otcong{C}_{2n}$ for any $m,m^{\prime }inmathcalF$, then $|mathcalF|leq(2(n-1)-1)!!$ and this bound is met with equality if and only if $mathcalF=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.

Full work available at URL: https://arxiv.org/abs/1409.2057

Recommendations

• An algebraic proof of the Erdős-Ko-Rado theorem for intersecting families of perfect matchings
• An extension of the Erdős-Ko-Rado theorem to set-wise 2-intersecting families of perfect matchings
• The Erdős-Ko-Rado theorem for 2-intersecting families of perfect matchings
• An Erdős-Ko-Rado theorem for matchings in the complete graph
• Stability for 1-intersecting families of perfect matchings

zbMATH Keywords

perfect matching of a complete graphsymmetric commutative association scheme

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Title not available (Why is that?)
• Four questions on Birkhoff polytopes
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Paths, Trees, and Flowers
• A new proof of the Erdős-Ko-Rado theorem for intersecting families of permutations
• On the maximum number of permutations with given maximal or minimal distance
• On Symmetrized Kronecker Powers and the Structure of the Free Lie Ring
• TWO THEOREMS IN GRAPH THEORY
• Intersecting families of permutations
• Brick decompositions and the matching rank of graphs
• Erdős-Ko-Rado theorems for uniform set-partition systems
• On the spectrum of the derangement graph
• Multiplicity-free permutation representations of the symmetric group.
• Solving the Ku-Wales conjecture on the eigenvalues of the derangement graph
• Eigenvalues of the derangement graph
• Structural Information and Communication Complexity
• Title not available (Why is that?)

Cited In (15)

• Stability for 1-intersecting families of perfect matchings
• The Erdős-Ko-Rado theorem for 2-intersecting families of perfect matchings
• Alternating sign property of the perfect matching derangement graph
• Erdős matching conjecture for almost perfect matchings
• On the intersection density of the symmetric group acting on uniform subsets of small size
• On the spectrum of the perfect matching derangement graph
• On cocliques in commutative Schurian association schemes of the symmetric group
• The absolute values of the perfect matching derangement graph's eigenvalues almost follow the lexicographic order of partitions
• Eigenvalues of the matching derangement graph
• An Erdős-Ko-Rado theorem for matchings in the complete graph
• The perfect matching association scheme
• An algebraic proof of the Erdős-Ko-Rado theorem for intersecting families of perfect matchings
• On the flip graphs on perfect matchings of complete graphs and signed reversal graphs
• An extension of the Erdős-Ko-Rado theorem to set-wise 2-intersecting families of perfect matchings
• An extension of the Erdős-Ko-Rado theorem to uniform set partitions

Uses Software

• GAP

This page was built for publication: Erdős-Ko-Rado for perfect matchings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2400976)