Star-optimality for cross-intersecting subfamilies of hereditary families: Borg's cross-intersecting analogue of Chvatal's conjecture

For a hereditary family (downset) H contained in 2^[n], Borg (2012) conjectured that the sum of sizes of k cross-intersecting subfamilies A_1,...,A_k of H is maximized by the star configuration A_1=...=A_k=S (a largest star of H) whenever k >= n+1 and H is non-trivial, and that the product of sizes is so maximized for every k >= 2. Each conjecture generalizes Chvátal's 1974 conjecture on largest intersecting subfamilies of hereditary families, which remains open. Proven cases are: families whose bases share a common element, the sum for k=2, and families compressed with respect to an element when k >= n+1 (with equality characterizations). The conjectures remain open in all remaining cases, in particular for general hereditary families (both sum and product) and for the product on compressed families when 2 <= k <= n, whose smallest instance k=2 the source itself identifies as the natural first target. The problem asks for proofs or explicit counterexamples, and for the structure of extremal configurations.

Background

A family H of subsets of a finite set is hereditary (also called a downset or simplicial complex) if every subset of a member of H is again a member; equivalently H is a union of power sets of its maximal members, which are called bases. The family of independent sets of a graph or matroid is a standard example. For an element x, the subfamily H = {F in H : x in F} of all members containing x is called a star of H. A family is intersecting if any two of its members meet, and families A_1,...,A_k are cross-intersecting if every set in A_i meets every set in A_j whenever i and j differ (the families may be empty and need not be internally intersecting).

For intersecting subfamilies of the full power set the classical bound |A| <= 2^(n-1) holds with stars extremal. In 1974 Chvátal conjectured the far-reaching generalization that every hereditary family H has a largest intersecting subfamily that is a star — equivalently |A| <= |S| for every intersecting subfamily A of H, where S is a largest star of H. This conjecture is still open. It is known for hereditary families that are left-compressed (closed under replacing an element j of a set by a smaller element i not already in it) — proved by Chvátal himself; for families compressed with respect to an element x (closed under replacing any element y by x) — proved by Snevily (1992); for families whose bases all share a common element; and for downsets of rank at most 3 (Czabarka, Hurlbert, Kamat 2017).

Borg (2012) introduced the natural cross-intersecting analogue. For k cross-intersecting subfamilies of a family there are two natural extremal parameters: the sum of their sizes and the product of their sizes (the product counts the k-tuples (A_1,...,A_k) obtained by choosing one member from each family). Using a classical pairing theorem stating that any hereditary family is a disjoint union of pairs of disjoint sets (possibly together with the empty set), together with the arithmetic mean-geometric mean inequality, Borg proved the universal bounds: the sum is at most k|H|/2 and the product at most (|H|/2)^k. He then conjectured:

• Conjecture 3.1 (sum): if k >= n+1 and H is a hereditary subfamily of 2^[n] different from {empty set}, then the sum is maximized by the star configuration A_1 = ... = A_k = S for a largest star S. The condition k >= n+1 cannot be dropped: for H = {empty set} union the singletons of [n] and 2 <= k < n+1, the configuration (H, empty, ..., empty) gives a larger sum.
• Conjecture 3.2 (stronger dichotomy): for any k, the maximum of the sum is attained by one of the two configurations (H, empty, ..., empty) or (S, ..., S).
• Conjecture 3.5 (product): for any hereditary H and any k >= 2, the product is maximized by the star configuration.

Borg proved all three conjectures when the bases of H share a common element; Conjecture 3.2 when k = 2; and, through newly discovered properties of the compression (shifting) operation, all three conjectures with full equality characterizations when H is compressed with respect to an element and k >= n+1. His companion work (Borg 2014) established for the product that the case k = 2 implies every k >= 2. Crucially, each of the three conjectures generalizes Chvátal's conjecture: taking A_1 = ... = A_k = A for an intersecting subfamily A of H yields |A| <= |S|. Any full resolution therefore settles Chvátal's conjecture.

What the paper left open is exactly the problem posed here: general hereditary families whose bases share no common element and which cannot be assumed compressed, for both the sum (k >= n+1) and the product (all k >= 2); the product for compressed families when 2 <= k <= n, whose smallest instance is k = 2; and the structure of extremal configurations beyond the compressed, large-k regime.

Problem Statement

Let $[n]=\{1,\dots,n\}$, and let $\mathcal{H}\subseteq 2^{[n]}$ be a hereditary family (a downset: every subset of a member is a member). For $x\in[n]$, the star $\mathcal{H}\langle x\rangle$ is the subfamily of all members of $\mathcal{H}$ containing $x$, and $s(\mathcal{H})=\max_{x\in[n]}|\mathcal{H}\langle x\rangle|$ is the size of a largest star. Subfamilies $\mathcal{A}_1,\dots,\mathcal{A}_k\subseteq\mathcal{H}$ are cross-intersecting if $A\cap B\neq\emptyset$ whenever $A\in\mathcal{A}_i$, $B\in\mathcal{A}_j$ and $i\neq j$. Determine the truth of Borg's conjectures:

1. (Sum, Conjecture 3.1) If $k\ge n+1$ and $\mathcal{H}\neq\{\emptyset\}$, is

$\sum_{i=1}^k|\mathcal{A}_i|\;\le\;k\,s(\mathcal{H})$

with the maximum attained by $\mathcal{A}_1=\dots=\mathcal{A}_k=\mathcal{S}$ for a largest star $\mathcal{S}$? More generally (Conjecture 3.2), let $\mathcal{H}$ be non-empty with $\mathcal{H}\neq\{\emptyset\}$ and let $k$ be arbitrary: is it true that the maximum of $\sum_i|\mathcal{A}_i|$ over all $k$ cross-intersecting subfamilies of $\mathcal{H}$ is attained by $(\mathcal{H},\emptyset,\dots,\emptyset)$ when $k\le|\mathcal{H}|/s(\mathcal{H})$, and by $(\mathcal{S},\dots,\mathcal{S})$ when $k\ge|\mathcal{H}|/s(\mathcal{H})$? (Borg notes this dichotomy is equivalent to saying that at least one of the two configurations always gives the maximum.)

2. (Product, Conjecture 3.5) For every hereditary $\mathcal{H}$ and every $k\ge2$, is

$\prod_{i=1}^k|\mathcal{A}_i|\;\le\;s(\mathcal{H})^k\,?$

By Borg's reduction, an affirmative answer for $k=2$ implies the answer for all $k\ge2$, so the decisive case is $k=2$.

3. (Smallest open case of the product conjecture) Does the inequality in item 2 hold when $k=2$ and $\mathcal{H}$ is compressed with respect to an element $x$ of $[n]$ (that is, replacing any element $y\ne x$ of a member of $\mathcal{H}$ by $x$ always yields another member; in particular when $\mathcal{H}$ is left-compressed, meaning that replacing an element $j$ of a member by a smaller element $i$ not already in it always yields another member)? The compressed case is currently proven only under the stronger hypothesis $k\ge n+1$.

4. (Extremal structure) In the regimes where the sum or product bound holds, determine all configurations attaining the bound. Equality characterizations are known only for $\mathcal{H}$ compressed with respect to an element and $k\ge n+1$; the degenerate family $\{\emptyset\}\cup\binom{[n]}{1}$ already exhibits two genuinely different extremal types for the sum.

Determine the truth of these statements in their stated generality, or for an explicitly identified class of hereditary families such as the compressed families of item 3, refuting any false statement by an explicit finite counterexample. Note that substituting $\mathcal{A}_1=\dots=\mathcal{A}_k=\mathcal{A}$ with $\mathcal{A}$ intersecting shows that a positive answer to item 1 or item 2 in full generality implies Chvátal's conjecture, so a proof for all hereditary families is expected to be at least as hard as that famous open problem; this implication is part of the problem's content.

References

1. Peter Borg, Cross-intersecting sub-families of hereditary families, Journal of Combinatorial Theory, Series A 119 (2012) 871-881, DOI 10.1016/j.jcta.2011.12.002 (arXiv:1103.3858), https://arxiv.org/abs/1103.3858
2. Peter Borg, The maximum sum and maximum product of sizes of cross-intersecting families, European Journal of Combinatorics 35 (2014) 117-130, DOI 10.1016/j.ejc.2013.06.029 (arXiv:1102.0667), https://arxiv.org/abs/1102.0667
3. V. Chvátal, Intersecting families of edges in hypergraphs having the hereditary property, in: Hypergraph Seminar (Columbus, Ohio 1972), Lecture Notes in Mathematics 411, Springer, Berlin, 1974, pp. 61-66, DOI 10.1007/bfb0066179, https://doi.org/10.1007/bfb0066179
4. Hunter Snevily, A new result on Chvátal's conjecture, Journal of Combinatorial Theory, Series A 61 (1992) 137-141, DOI 10.1016/0097-3165(92)90059-4, https://doi.org/10.1016/0097-3165(92)90059-4
5. Peter Borg, Cross-intersecting subfamilies of levels of hereditary families, Discrete Mathematics 343 (2020) 111900, DOI 10.1016/j.disc.2020.111900 (arXiv:1805.05241), https://arxiv.org/abs/1805.05241
6. Peter Borg, Cross-intersecting non-empty uniform subfamilies of hereditary families, European Journal of Combinatorics 78 (2019) 256-267, DOI 10.1016/j.ejc.2019.02.006 (arXiv:1806.01093), https://arxiv.org/abs/1806.01093
7. Andrey Kupavskii, Intersection theorems for uniform subfamilies of hereditary families, arXiv:2311.02246 (2023), https://arxiv.org/abs/2311.02246
8. Ehud Friedgut, Jeff Kahn, Gil Kalai, Nathan Keller, Chvátal's conjecture and correlation inequalities, Journal of Combinatorial Theory, Series A 156 (2018) 22-43, DOI 10.1016/j.jcta.2017.11.015 (arXiv:1608.08954), https://arxiv.org/abs/1608.08954
9. Fan Chang, Hong Liu, Miao Liu, The sharp diagonal spectral correlation inequality on the discrete cube, arXiv:2606.32024 (2026), https://arxiv.org/abs/2606.32024
10. Jesse Looney, Jonah McDonald, Allison Klingler, Gloria Wu, Jonad Pulaj, Haoze Wu, Solution Space Partitioning for Extremal Set Theory, arXiv:2608.06432 (2026), https://arxiv.org/abs/2608.06432
11. Eva Czabarka, Glenn Hurlbert, Vikram Kamat, Chvátal's conjecture for downsets of small rank, arXiv:1703.00494 (2017), https://arxiv.org/abs/1703.00494
12. Jorge Alberto Olarte, Francisco Santos, Jonathan Spreer, Short proof of two cases of Chvátal's conjecture, Discrete Mathematics 342 (2019) 2192-2194, DOI 10.1016/j.disc.2019.04.011 (arXiv:1804.03646), https://arxiv.org/abs/1804.03646
13. Norihide Tokushige, When are stars the largest cross intersecting families?, arXiv:1810.06820 (2018), https://arxiv.org/abs/1810.06820
14. Yang Huang, Yuejian Peng, Jian Wang, The maximum sum of sizes of non-empty pairwise cross-intersecting families, Journal of Combinatorial Theory, Series B 178 (2026) 145-163, DOI 10.1016/j.jctb.2025.12.004, https://doi.org/10.1016/j.jctb.2025.12.004
15. Jonathan Cary, Some results on Kleitman's conjecture, arXiv:2402.03150 (2024), https://arxiv.org/abs/2402.03150