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

Abstract

Let $M_n=M(K_{n+1})$ be the graphic matroid of the complete graph, and let ${\mathcal{F}}_k(M_n)$ be its rank-$k$ flats. We study families $\mathcal{A}\subseteq {\mathcal{F}}_k(M_n)$ satisfying $\mathrm{rk}(A\wedge B)\ge t$ for all $A,B\in \mathcal{A}$. 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~\cite{ErdosSzekelyHigher}. We prove the corresponding Erdős--Ko--Rado theorem in the explicit linear range $n+1\ge 8k$, giving a constant-factor advance toward the conjectured sharp range $n\ge 2k$. For every fixed $t$, we further prove an Erdős--Ko--Rado theorem under an explicit condition of order $O_t(k^2)$ 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^6)$ threshold and characterize the unique extremal family up to isomorphism.