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

2021/10/05 by Mahsa N. Shirazi, Shirazi, Mahsa N.
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2110.02175

openalex publication_date 2021/10/05 · openalex created_date 2024/04/10 · openalex updated_date 2026/07/28

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₁, ⋯, P_t in P and Q₁, ⋯, Q_t in Q such that the union of edges P₁, ⋯, P_t has the same set of vertices as the union of Q₁, ⋯, Q_t has. In this paper we prove an extension of the famous Erdő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 t≥ 2.

Related

• The Erdős-Ko-Rado theorem for 2-intersecting families of perfect matchings
• The Erdos-Ko-Rado theorem for perfect matchings
• On intersecting families of subgraphs of perfect matchings
• On k-wise intersecting families of vertex sets in perfect matchings
• Intersection theorems for families of matchings of complete k-partite k-graphs