Erdős--Ko--Rado and Hilton--Milner Theorems in the Partition Lattice

2026/08/06 by Mengyu Cao, Jiaqi Liao, Haixiang Zhang · 1 voice
Mathematics · #math.CO

paper · pdf

arxiv created 2026/08/06 · arxiv updated 2026/08/07

Abstract

Let M_n=M(K_n+1) be the graphic matroid of the complete graph, and let F_k(M_n) be its rank-k flats. We study families A\subseteqF_k(M_n) satisfying rk(A\wedge B)≥ t for all A,B\inA. For t=1, this problem is exactly equivalent to Czabarka's partition-EKR conjecture, first introduced in print by P.~L. Erdős and L.~A. Székely~\citeErdosSzekelyHigher. We prove the corresponding Erdős--Ko--Rado theorem in the explicit linear range n+1≥8k, giving a constant-factor advance toward the conjectured sharp range n≥2k. For every fixed t, we further prove an Erdős--Ko--Rado theorem under an explicit condition of order O_t(k²) on the block number n+1-k, with equality only for a full t-star. We also determine the largest nontrivial intersecting families under an explicit O(k⁶) threshold and characterize the unique extremal family up to isomorphism.

Citations

• Spread approximations for forbidden intersections problems
• An Extension of the Erdős-Ko-Rado Theorem to uniform set partitions
• Thresholds versus fractional expectation-thresholds
• Coding for Sunflowers
• Improved bounds for the sunflower lemma
• Improved bounds for the sunflower lemma
• SOME INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS

Discussions

• build seating charts where each new one must share at least one seatmate pair with all the old ones. how large a family can you grow? the paper proves once you hit a threshold, seating one specific pa [bsky, 0 points, 0 comments]