For an integer $d \geq 2$, a family $\mathcal{ F}$ of sets is $\textit{ $d$-wise intersecting}$ if for any distinct sets $A_1,A_2,\dots,A_d \in \mathcal{ F}$, $A_1 \cap A_2 \cap \dots \cap A_d \neq \emptyset$, and $\textit{ non-trivial}$ if $\bigcap \mathcal{ F} = \emptyset$. Hilton and Milner conjectured that for $k \geq d \geq 2$ and large enough $n$, the extremal non-trivial $d$-wise intersecting family of $k$-element subsets of $[n]$ is one of the following two families: \begin{ align*} &\mathcal{ H}(k,d) = \{ A \in \binom{ [n]}{ k} : [d-1] \subset A, A \cap [d,k+1] \neq \emptyset\} \cup \{ [k+1] \setminus \{ i \} : i \in [d - 1]\} \\ &\mathcal{ A}(k,d) = \{ A \in \binom{ [n]}{ k} : |A \cap [d+1]| \geq d \}. \end{ align*} The celebrated Hilton-Milner Theorem states that $\mathcal{ H}(k,2)$ is the unique extremal non-trivial intersecting family for $k>3$. We prove the conjecture and prove a stability theorem, stating that any large enough non-trivial $d$-wise intersecting family of $k$-element subsets of $[n]$ is a subfamily of $\mathcal{ A}(k,d)$ or $\mathcal{ H}(k,d)$.

Categories: math.CO

Non-trivial $d$-wise Intersecting families