The $d$-degree Erdős–Ko–Rado conjecture in the optimal range $n \ge 2k+1$

Huang and Zhang proved that for integers $k > d \ge 2$ and $n \ge 2k+2d-3$, every intersecting family $\mathcal{F} \subseteq \binom{[n]}{k}$ has minimum $d$-degree at most $\binom{n-d-1}{k-d-1}$, and conjectured that the same bound holds under the optimal hypothesis $n \ge 2k+1$ for all integers $k > d \ge 0$. The cases $d = 0, 1, 2$ are known for the full range, and subsequent work has improved the threshold only for $d$ very close to $k$ ($n \ge 2k+\sqrt{2k}+O(1)$ for $d = k-1$ and $n \ge 2k+7k^{2/3}+O(k^{1/3})$ for $d = k-2$), while the vector-space ($q$-analogue) version has been settled in the full range. The problem is to prove or refute the conjecture in the remaining region $3 \le d \le k-1$ with $2k+1 \le n < 2k+2d-3$ (with correspondingly tighter gaps, asymptotically in $k$, when $d$ is close to $k$).

Background

Write $[n]$ for $\{1,\dots,n\}$ and $\binom{[n]}{k}$ for the family of all $k$-subsets of $[n]$. A family $\mathcal{F}$ of sets is called intersecting if any two of its members share at least one element. Viewing $\mathcal{F} \subseteq \binom{[n]}{k}$ as a $k$-uniform hypergraph on $n$ vertices, the classical Erdős–Ko–Rado theorem (Erdős, Ko, Rado, 1961) states that for $n \ge 2k$ an intersecting family has size at most $\binom{n-1}{k-1}$; the bound is attained by the 1-star, the family of all $k$-sets containing a fixed element, and for $n \ge 2k+1$ the 1-star is the unique extremal example up to relabeling. For a set $S \subseteq [n]$ the $S$-degree of $\mathcal{F}$ is the number of members of $\mathcal{F}$ that contain $S$, and the minimum $d$-degree $\delta_d(\mathcal{F})$ is the minimum of the $S$-degree over all $d$-subsets $S$ of $[n]$; thus $\delta_0(\mathcal{F}) = |\mathcal{F}|$ and $\delta_1$ is the usual minimum vertex degree. In this language the Erdős–Ko–Rado theorem determines the maximum of $\delta_0$ over intersecting families, and a natural degree analogue, motivated by Dirac-type questions for hypergraphs, asks for the maximum of $\delta_d$. Huang and Zhao (2017) settled $d = 1$: for $n \ge 2k+1$, every intersecting $\mathcal{F} \subseteq \binom{[n]}{k}$ satisfies $\delta_1(\mathcal{F}) \le \binom{n-2}{k-2}$, with both the range and the bound best possible — at $n = 2k$ there exist regular intersecting families of size $\binom{2k-1}{k-1}$ for most $k$ (Ihringer and Kupavskii, 2019), so $n \ge 2k+1$ is the exact threshold. Note that the 1-star attains $\delta_d = \binom{n-d-1}{k-d-1}$ for every $d < k$, the minimum being achieved by the $d$-sets avoiding the star center. For general $d$, Kupavskii (2019) proved $\delta_d(\mathcal{F}) \le \binom{n-d-1}{k-d-1}$ for $n \ge 2k + 3d/(1 - d/k)$, a bound that becomes quadratic in $k$ when $d$ is close to $k$. Huang and Zhang (arXiv 2024; published in J. Combin. Theory Ser. A, 2026) improved this to $n \ge 2k+2d-3$ for all $k > d \ge 2$, using spectral graph theory: they decompose the indicator vector of $\mathcal{F}$ along the eigenspaces of the Kneser graph $KG(n,k)$ (whose vertices are the $k$-subsets of $[n]$, with an edge between two disjoint $k$-sets) and combine a Hoffman-type spectral inequality (a bound of the kind used to upper-bound independent sets in a graph by its eigenvalues) encoding intersectingness with a counting inequality encoding large minimum $d$-degree. Their argument already yields the $d = 2$ case in the full range $n \ge 2k+1$, so combined with $d = 0$ (Erdős–Ko–Rado) and $d = 1$ (Huang–Zhao) the conjecture below is verified for $d \in \{0,1,2\}$. The boundary behavior is delicate: at $n = 2k$ the desired conclusion already fails (a $2$-$(6,3,2)$ design on $[6]$ — ten triples in which every pair of points lies in exactly two of them — is intersecting with $\delta_2 = 2 > \binom{3}{0} = 1$), and at $n = 2k+1$ extremal families other than the 1-star exist (the Fano plane — the seven triples forming the projective plane of order $2$ — for $(n,k,d) = (7,3,2)$, and a design-based construction for $(9,4,2)$ achieving $\delta_2 = 6 = \binom{n-3}{k-3}$), so the uniqueness and stability phenomena available for $d = 1$ do not directly generalize. After the source paper, Gan, Han and Im (2026) improved the threshold for $d$ close to $k$ — to $n \ge 2k+\sqrt{2k}+O(1)$ for $d = k-1$ and $n \ge 2k+7k^{2/3}+O(k^{1/3})$ for $d = k-2$ — via structural arguments, and Shan and Zhou (2025) proved the $q$-analogue of the full conjecture for vector spaces, where $\binom{[n]}{k}$ is replaced by the family of $k$-dimensional subspaces of an $n$-dimensional space over a finite field and binomial coefficients by Gaussian binomial coefficients (the subspace-counting analogues of binomial coefficients): for $k > d \ge 2$ and $n \ge 2k+1$, every intersecting family of subspaces has minimum $d$-degree at most $\binom{n-d-1}{k-d-1}_q$. The original set-family conjecture, however, remains open.

Problem Statement

Prove or refute the following conjecture of Huang and Zhang. For all integers $k > d \ge 0$ and $n \ge 2k+1$, every intersecting family $\mathcal{F} \subseteq \binom{[n]}{k}$ satisfies

$$\delta_d(\mathcal{F}) \le \binom{n-d-1}{k-d-1},$$

where $\delta_d(\mathcal{F}) = \min_{S \in \binom{[n]}{d}} \left|\{F \in \mathcal{F} : S \subseteq F\}\right|$ is the minimum $d$-degree of $\mathcal{F}$. A solution must settle the statement exactly as quantified, with no added hypotheses on $n$, $k$, $d$, or the structure of $\mathcal{F}$. The claim is already known for $d \in \{0,1,2\}$ for all $n \ge 2k+1$ (Erdős–Ko–Rado; Huang–Zhao; the source paper's own observation), for all $d \ge 2$ when $n \ge 2k+2d-3$ (Huang–Zhang), and for $d = k-1$ when $n \ge 2k+\sqrt{2k}+O(1)$ and $d = k-2$ when $n \ge 2k+7k^{2/3}+O(k^{1/3})$ (Gan–Han–Im); the genuinely open region is $3 \le d \le k-1$ with $2k+1 \le n < 2k+2d-3$ (with the correspondingly tighter gaps for $d \in \{k-1, k-2\}$ holding asymptotically in $k$; for any given $(k,d)$ the settled region extends to the strongest published threshold). A refutation consists of an explicit intersecting family $\mathcal{F} \subseteq \binom{[n]}{k}$ with integers $k > d \ge 0$ and $n \ge 2k+1$ for which every $d$-subset of $[n]$ is contained in strictly more than $\binom{n-d-1}{k-d-1}$ members of $\mathcal{F}$.

References

1. Hao Huang, Yi Zhang, "On a $d$-degree Erdős–Ko–Rado Theorem", Journal of Combinatorial Theory, Series A, vol. 221, article 106163 (2026). DOI: 10.1016/j.jcta.2026.106163; arXiv:2407.14091, https://arxiv.org/abs/2407.14091
2. Luyining Gan, Jie Han, Seonghyuk Im, "Note on the codegree version of the Erdős–Ko–Rado theorem", arXiv:2605.17945 (2026), https://arxiv.org/abs/2605.17945
3. Yunjing Shan, Junling Zhou, "$d$-degree Erdős-Ko-Rado theorem for finite vector spaces", Acta Mathematica Hungarica, vol. 176, no. 1, pp. 215–235 (2025). DOI: 10.1007/s10474-025-01543-1; arXiv:2411.17985, https://arxiv.org/abs/2411.17985
4. Hao Huang, Yi Zhao, "Degree versions of the Erdős–Ko–Rado theorem and Erdős hypergraph matching conjecture", Journal of Combinatorial Theory, Series A, vol. 150 (2017), 233–247. DOI: 10.1016/j.jcta.2017.03.006, https://doi.org/10.1016/j.jcta.2017.03.006
5. Andrey Kupavskii, "Degree versions of theorems on intersecting families via stability", Journal of Combinatorial Theory, Series A, vol. 168 (2019), 272–287. DOI: 10.1016/j.jcta.2019.06.002, https://doi.org/10.1016/j.jcta.2019.06.002
6. P. Erdős, Chao Ko, R. Rado, "Intersection theorems for systems of finite sets", The Quarterly Journal of Mathematics, vol. 12, no. 1, pp. 313–320 (1961). DOI: 10.1093/qmath/12.1.313, https://doi.org/10.1093/qmath/12.1.313
7. V. Chvátal, "Intersecting families of edges in hypergraphs having the hereditary property", in: Hypergraph Seminar (Ohio State Univ., 1972), Lecture Notes in Mathematics, vol. 411, Springer, Berlin (1974), pp. 61–66. DOI: 10.1007/BFb0066179, https://doi.org/10.1007/bfb0066179
8. Ferdinand Ihringer, Andrey Kupavskii, "Regular intersecting families", Discrete Applied Mathematics, vol. 270 (2019), 142–152. DOI: 10.1016/j.dam.2019.07.009, https://doi.org/10.1016/j.dam.2019.07.009