An extension of the Erdős-Ko-Rado theorem to set-wise 2-intersecting families of perfect matchings

DOI10.1016/J.DISC.2023.113444MaRDI QIDQ6041562zbMATH OpenOpenAlexWikidataFDO

Authors Mahsa N. Shirazi

Publication date 31 May 2023

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

association schemecocliqueErdős-Ko-Rado theoremperfect matchingsquotient graphsratio bound

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Extremal set theory (05D05) Association schemes, strongly regular graphs (05E30)

Abstract: Two perfect matchings $P$ and $Q$ of the complete graph on $2k$ vertices are said to be set-wise $t$-intersecting if there exist edges $P_1,cdots,P_t$ in $P$ and $Q_1,cdots,Q_t$ in $Q$ such that the union of edges $P_1,cdots,P_t$ has the same set of vertices as the union of $Q_1,cdots,Q_t$ has. In this paper we prove an extension of the famous ErdH{o}s-Ko-Rado (EKR) theorem to set-wise $2$-intersecting families of perfect matching on all values of $k$, and we conjecture similar statement for all $tgeq2$.

Recommendations

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

Cites work

• A new proof of the Erdős-Ko-Rado theorem for intersecting families of permutations
• An algebraic proof of the Erdős-Ko-Rado theorem for intersecting families of perfect matchings
• An extension of the Erdoes, Ko, Rado theorem to t-designs
• Erdős-Ko-Rado for perfect matchings
• Erdős-Ko-Rado theorems for permutations and set partitions
• Erdős-Ko-Rado theorems for uniform set-partition systems
• Erdős-Ko-Rado theorems. Algebraic approaches
• scientific article; zbMATH DE number 645265 (Why is no real title available?)
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• On the minimal degrees of characters of \(S_n\)
• Setwise intersecting families of permutations
• The Erdős-Ko-Rado theorem for 2-intersecting families of perfect matchings
• The Erdős-Ko-Rado theorem for vector spaces
• The exact bound in the Erdős-Ko-Rado theorem
• The perfect matching association scheme

Cited in

(5)

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

This page was built for publication: An extension of the Erdős-Ko-Rado theorem to set-wise 2-intersecting families of perfect matchings

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