An Extension of the Erdős-Ko-Rado Theorem to uniform set partitions

2021/08/17 by Karen Meagher, Meagher, Karen, Mahsa N. Shirazi +3 · 1 citation
Economics, Econometrics and Finance · Mathematics · #05C25 #05C50 #05E30 #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Italy: Economic History and Contemporary Issues #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2108.07692

openalex publication_date 2021/08/17 · openalex created_date 2024/04/11 · openalex updated_date 2026/07/28

Abstract

A (k,ℓ)-partition is a set partition which has ℓ blocks each of size k. Two uniform set partitions P and Q are said to be partially t-intersecting if there exist blocks P_i in P and Q_j in Q such that | P_i ∩ Q_j |≥ t. In this paper we prove a version of the Erdős-Ko-Rado theorem for partially 2-intersecting (k,ℓ)-partitions. In particular, we show for ℓ sufficiently large, the set of all (k,ℓ)-partitions in which a block contains a fixed pair is the largest set of 2-partially intersecting (k,ℓ)-partitions. For for k=3, we show this result holds for all ℓ.

Cited by

• On the second largest eigenvalue of certain graphs in the perfect matching association scheme

Related

• Erdős-Ko-Rado theorem and Hilton-Milner type theorem for k-partitions
• Erd\H os--Ko--Rado type results for partitions via spread approximations
• A general 2-part Erd\H os-Ko-Rado theorem
• Cross-intersection theorems for uniform partitions of finite sets
• Short injective proofs of the Erdős-Ko-Rado and Hilton-Milner Theorem: A canonical partition of shifted intersecting set systems