Erdős-Ko-Rado for perfect matchings

DOI10.1016/J.EJC.2017.05.005MaRDI QIDQ2400976zbMATH OpenOpenAlexFDO

Authors Nathan Lindzey

Publication date 31 August 2017

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

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

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)

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.

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

Cites work

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

Cited in

(15)

• Stability for 1-intersecting families of perfect matchings
• An extension of the Erdős-Ko-Rado theorem to uniform set partitions
• 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

Describes a project that uses

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)