Sharp base-size thresholds for cross-intersecting subfamilies of levels of hereditary families

Borg (Discrete Mathematics, 2020) proved that for a hereditary family $\mathcal{H}$ (an abstract simplicial complex, e.g. the independent sets of a graph) whose smallest maximal member has size $\mu(\mathcal{H})$ at least a threshold $n_S(r,t)$ of degree $2t+3$ in $r$, any $k$ cross-$t$-intersecting subfamilies of a union of levels $\mathcal{F}=\bigcup_{s\in S}\mathcal{H}^{(s)}$ have total size at most $\max\{k|\mathcal{L}|,|\mathcal{F}|\}$, where $\mathcal{L}$ is a largest $t$-star of $\mathcal{F}$, with a complete equality characterization; in particular, two cross-intersecting subfamilies of the $r$-th level satisfy $|\mathcal{A}|+|\mathcal{B}|\leq|\mathcal{H}^{(r)}|$ once $\mu(\mathcal{H})\geq n_S(r,1)$. This record poses the sharp-threshold problem that work left open: does the same extremal dichotomy already hold at the natural thresholds familiar from the uniform power-set case — $\mu(\mathcal{H})\geq(t+1)(r-t+1)$ in general (Borg's 2009 $t$-star conjecture for unions of levels and its cross-intersection sum form) and $\mu(\mathcal{H})\geq 2r$ for two families (Borg's Conjecture 2.8, generalizing Kamat's 2011 conjecture for independent sets of graphs) — and is equality for $\mu(\mathcal{H})>2r$ attained only in the rigid configuration where one family is the whole $r$-th level and the other is empty? Both threshold conjectures remain open; the best known sufficient conditions are Borg's polynomial thresholds $n_S(r,t)$ and, on the single-family side, Kupavskii's near-linear bound $\mu\geq Crt\log^2(\mu/r)$.

Background

An Erdős–Ko–Rado (EKR) type question asks how large a family of sets can be when any two of its members share at least $t$ elements. The classical theorem of Erdős, Ko and Rado (1961), made sharp by Wilson (1984), states that for the family $\binom{[n]}{r}$ of all $r$-element subsets of an $n$-element set, a largest $t$-intersecting subfamily is a $t$-star (all $r$-sets containing a fixed $t$-element set) exactly when $n\geq(t+1)(r-t+1)$; below that threshold other configurations are larger, so $(t+1)(r-t+1)$ is the exact uniform threshold. In the cross-intersection variant one is given families $\mathcal{A}_1,\dots,\mathcal{A}_k$ such that every set of $\mathcal{A}_i$ meets every set of $\mathcal{A}_j$ ($i\neq j$) in at least $t$ elements, and one maximizes the sum (or product) of their sizes. Hilton (1977) proved the basic two-family sum theorem for the uniform level: if $n\geq 2r$ and $\mathcal{A},\mathcal{B}\subseteq\binom{[n]}{r}$ are cross-intersecting, then $|\mathcal{A}|+|\mathcal{B}|\leq\binom{n}{r}$, with equality for $n>2r$ only in the rigid configuration where one family is the entire level and the other is empty; at the borderline $n=2r$ a pair of equal stars also ties. Wang and Zhang (2011) settled the general-$t$ uniform sum problem.

The setting of this problem replaces the power set by a hereditary family $\mathcal{H}$: a family closed under taking subsets, equivalently an abstract simplicial complex, with natural examples being the family of independent sets of a graph or of a matroid. A maximal member of $\mathcal{H}$ is called a base, and $\mu(\mathcal{H})$ denotes the size of a smallest base. The $r$-th level $\mathcal{H}^{(r)}$ is the subfamily of $r$-element members. Holroyd and Talbot (2005) conjectured that for the independent-set family $\mathcal{I}_G$ of a graph, $r\leq\mu(\mathcal{I}_G)/2$ forces the largest intersecting subfamilies of $\mathcal{I}_G^{(r)}$ to be stars; this remains open in general. Borg (2009) extended the conjecture to arbitrary hereditary families, unions of levels, and general $t$: if $\mu(\mathcal{H})\geq(t+1)(r-t+1)$, then $\bigcup_{s\in S}\mathcal{H}^{(s)}$ should have the $t$-star property (some largest $t$-intersecting subfamily is a $t$-star $\mathcal{F}\langle T\rangle=\{F\in\mathcal{F}:T\subseteq F\}$, $|T|=t$), strictly so outside borderline cases; the threshold is best possible already for power sets. Kamat (2011) proposed the two-family cross-intersection analogue for graphs: if $\mu(\mathcal{I}_G)\geq 2r$ and $\mathcal{A},\mathcal{B}\subseteq\mathcal{I}_G^{(r)}$ are cross-intersecting, then $|\mathcal{A}|+|\mathcal{B}|\leq|\mathcal{I}_G^{(r)}|$.

Borg (2020) proved the cross-$t$-intersection sum theorem for unions of levels of hereditary families: if $\mu(\mathcal{H})\geq n_S(r,t)$, where $m(r,t)=\max\{2r,\frac{(r-t)(r-t+5)}{2}+t-1\}$ and $n_S(r,t)=(r-t+1)\binom{m(r,t)}{t+1}+r$ (already quintic in $r$ for $t=1$), then any $k$ cross-$t$-intersecting subfamilies $\mathcal{A}_i$ of $\mathcal{F}=\bigcup_{s\in S}\mathcal{H}^{(s)}$ satisfy $\sum_i|\mathcal{A}_i|\leq\max\{k|\mathcal{L}|,|\mathcal{F}|\}$ with $\mathcal{L}$ a largest $t$-star of $\mathcal{F}$, and equality holds only in three configurations: all $\mathcal{A}_i$ equal to a largest $t$-star; one family equal to $\mathcal{F}$ and the rest empty; or a tie between these. Specializing gives the two-family bound for $\mu(\mathcal{H})\geq n_S(r,1)$. The difficulty is that hereditary families have no symmetry: the standard tools of uniform intersection theory — the EKR shifting (compression) technique and Katona's cycle method — break down, and Borg's proof instead combines a bounded-witness lemma for non-trivial $t$-intersecting families with shadow-counting inequalities of Sperner type; these arguments lose polynomial factors, which is why the hypothesis sits far above the conjectured natural thresholds.

Problem Statement

Determine the sharp base-size thresholds at which the uniform power-set extremal structure for cross-intersection sums persists for arbitrary hereditary families. Concretely, prove or refute the following two statements, which assert that the classical uniform thresholds transfer verbatim to every abstract simplicial complex: statement (1) is Conjecture 2.8 of Borg (2020) verbatim, while statement (2) is the natural cross-intersection sum form at the threshold Borg explicitly conjectures for the single-family $t$-star property (his Conjecture 1.2, originating in Borg 2009), equivalently the sharp form of his Theorem 2.1.

(1) Two-family threshold (Conjecture 2.8, generalizing Kamat's conjecture for graphs). If $\mathcal{H}$ is a hereditary family with $\mu(\mathcal{H})\geq 2r$ and $\mathcal{A},\mathcal{B}\subseteq\mathcal{H}^{(r)}$ are cross-intersecting (every member of $\mathcal{A}$ intersects every member of $\mathcal{B}$; the families may be empty, equal, or trivial), must $|\mathcal{A}|+|\mathcal{B}|\leq|\mathcal{H}^{(r)}|$ hold? If moreover $\mu(\mathcal{H})>2r$, must equality be attained only in the rigid configuration $\{\mathcal{A},\mathcal{B}\}=\{\mathcal{H}^{(r)},\emptyset\}$?

(2) Natural-threshold sum theorem for unions of levels (the sharp form of Borg's Theorem 2.1). For integers $1\leq t\leq r$, $k\geq 2$, and $\emptyset\neq S\subseteq[t,r]$, let $\mathcal{F}=\bigcup_{s\in S}\mathcal{H}^{(s)}$ and let $\mathcal{L}$ be a largest $t$-star of $\mathcal{F}$. If $\mu(\mathcal{H})\geq(t+1)(r-t+1)$, must any $k$ cross-$t$-intersecting subfamilies $\mathcal{A}_1,\dots,\mathcal{A}_k\subseteq\mathcal{F}$ satisfy $\sum_{i=1}^{k}|\mathcal{A}_i|\leq\max\{k|\mathcal{L}|,|\mathcal{F}|\},$ with equality only in the three configurations of the theorem (all families equal to a largest $t$-star; one family equal to $\mathcal{F}$ and the rest empty; or a tie)? Its single-family shadow is Borg's 2009 Conjecture 1.2: if $\mu(\mathcal{H})\geq(t+1)(r-t+1)$, does $\bigcup_{s\in S}\mathcal{H}^{(s)}$ have the $t$-star property, strictly so when $\mu(\mathcal{H})>(t+1)(r-t+1)$ or $S\neq\{r\}$?

Both thresholds are best possible for the power set $\mathcal{H}=2^{[n]}$ (where $\mu(\mathcal{H})=n$) by Wilson's exact bound and Hilton's theorem, and the task includes establishing the exact optimal base-size threshold functions (conjecturally $(t+1)(r-t+1)$ in general and $2r$ for two families): prove sufficiency at the claimed value and provide explicit hereditary families showing that no smaller value can suffice. A positive answer to the general sum statement implies the single-family $t$-star conjecture by taking $k>|\mathcal{F}|/|\mathcal{L}|$. Each sub-claim is independently refutable by an explicit hereditary family — the inequality and the rigidity clause in (1), the sum inequality and the equality classification in (2), the single-family $t$-star property of (2)’s shadow, and the sufficiency of a claimed threshold value — and refuting any one resolves that target; refuting an inequality settles the equality clause attached to it, while a positive answer to (1) or (2) is complete only together with its equality characterization.

References

1. Peter Borg, Cross-intersecting subfamilies of levels of hereditary families, Discrete Mathematics 343(8):111900 (2020), DOI 10.1016/j.disc.2020.111900, https://arxiv.org/abs/1805.05241.
2. Peter Borg, Extremal t-intersecting sub-families of hereditary families, Journal of the London Mathematical Society (2) 79:167–185 (2009), DOI 10.1112/jlms/jdn062, https://doi.org/10.1112/jlms/jdn062.
3. Vikram Kamat, On cross-intersecting families of independent sets in graphs, Australasian Journal of Combinatorics 50:171–181 (2011), arXiv:1010.0947, https://arxiv.org/abs/1010.0947.
4. Fred Holroyd and John Talbot, Graphs with the Erdős–Ko–Rado property, Discrete Mathematics 293:165–176 (2005), DOI 10.1016/j.disc.2004.08.028, https://doi.org/10.1016/j.disc.2004.08.028.
5. A. J. W. Hilton, An intersection theorem for a collection of families of subsets of a finite set, Journal of the London Mathematical Society (2) 15:369–376 (1977), DOI 10.1112/jlms/s2-15.3.369, https://doi.org/10.1112/jlms/s2-15.3.369.
6. P. Erdős, Chao Ko and R. Rado, Intersection theorems for systems of finite sets, Quarterly Journal of Mathematics 12:313–320 (1961), DOI 10.1093/qmath/12.1.313, https://doi.org/10.1093/qmath/12.1.313.
7. Richard M. Wilson, The exact bound in the Erdős–Ko–Rado theorem, Combinatorica 4:247–257 (1984), DOI 10.1007/BF02579226, https://doi.org/10.1007/BF02579226.
8. Jun Wang and Huajun Zhang, Cross-intersecting families and primitivity of symmetric systems, Journal of Combinatorial Theory, Series A 118:455–462 (2011), DOI 10.1016/j.jcta.2010.09.005, https://doi.org/10.1016/j.jcta.2010.09.005.
9. Peter Borg, Cross-intersecting non-empty uniform subfamilies of hereditary families, European Journal of Combinatorics 78:256–267 (2019), DOI 10.1016/j.ejc.2019.02.006, https://arxiv.org/abs/1806.01093.
10. Andrey Kupavskii, Intersection theorems for uniform subfamilies of hereditary families (2023), arXiv:2311.02246, https://arxiv.org/abs/2311.02246.
11. Péter Frankl and Glenn Hurlbert, On the Holroyd–Talbot conjecture for sparse graphs, Discrete Mathematics 347:113742 (2024), DOI 10.1016/j.disc.2023.113742, https://arxiv.org/abs/2207.01661.
12. Glenn Hurlbert, A Survey of the Holroyd–Talbot Conjecture (2025), arXiv:2501.16144, https://arxiv.org/abs/2501.16144.
13. Denys Bulavka and Russ Woodroofe, Strict Erdős–Ko–Rado theorems for simplicial complexes (2025), arXiv:2503.15608, https://arxiv.org/abs/2503.15608.
14. Huajun Zhang and Huihui Zhang, Non-trivial intersecting and non-empty cross-intersecting families of independent sets in graphs, Discrete Mathematics 349:115113 (2026), DOI 10.1016/j.disc.2026.115113, https://doi.org/10.1016/j.disc.2026.115113.