Two results on set families: sturdiness and intersection
Pith reviewed 2026-05-18 21:40 UTC · model grok-4.3
The pith
Every IU-family of subsets has sturdiness at most 2 to the power of n minus 4.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The paper shows that if F is an IU-family in the power set of an n-element set, then its sturdiness β(F) is at most 2^{n-4}. It further gives a tight upper bound on the sum of the sizes of two cross t-intersecting separated families and supplies explicit counterexamples to an open problem posed by Frankl, Liu, Wang and Yang.
What carries the argument
Sturdiness β(F), defined as the minimum over all i ≠ j of the size of F(i, bar j), the collection of sets in F that contain i but not j, each with i removed.
If this is right
- The known size bound of 2^{n-2} for IU-families is now joined by a uniform lower bound on how many sets must be asymmetric with respect to every pair of elements.
- The combined size of any two cross t-intersecting separated families is capped by a specific tight expression.
- The open problem on separated families is settled negatively by the counterexamples given.
Where Pith is reading between the lines
- The sturdiness bound may make it easier to classify the largest possible IU-families by ruling out overly lopsided distributions.
- The counterexamples suggest that the extremal size for cross t-intersecting pairs can grow differently once t increases beyond 1.
- Similar minimum-size tracking arguments could be applied to other pairs of constraints on set families.
Load-bearing premise
The minimum size of sets containing one element but not the other correctly reflects the global limits imposed by requiring every pair to intersect yet forbidding any pair from covering the entire ground set.
What would settle it
An explicit IU-family on n elements in which the smallest F(i, bar j) exceeds 2^{n-4} for some pair i and j would disprove the bound.
read the original abstract
This paper resolves two open problems in extremal set theory. For a family $\mathcal{F} \subseteq 2^{[n]}$ and $i, j\in [n]$, we denote $\mathcal{F} (i,\bar{j})=\{F\backslash\{i\}: F\in \mathcal{F}, F\cap\{i,j\}=\{i\}\}$. The sturdiness $\beta (\mathcal{F})$ is defined as the minimum $|\mathcal{F} (i,\bar{j})|$ over all $i\neq j$. A family $\mathcal{F}$ is called an IU-family if it satisfies the intersection constraint: $F\cap F'\neq \emptyset $ for all $F,F'\in \mathcal{F}$, as well as the union constraint: $F\cup F' \neq [n]$ for all $F,F'\in \mathcal{F}$. The well-known IU-Theorem states that every IU-family $\mathcal{F}\subseteq 2^{[n]}$ has size at most $ 2^{n-2}$. In this paper, we prove that if $\mathcal{F}\subseteq 2^{[n]}$ is an IU-family, then $\beta (\mathcal{F})\le 2^{n-4}$. This confirms a recent conjecture proposed by Frankl and Wang. As the second result, we establish a tight upper bound on the sum of sizes of cross $t$-intersecting separated families. Our result not only extends a previous theorem of Frankl, Liu, Wang and Yang on separated families, but also provides explicit counterexamples to an open problem proposed by them, thereby settling their problem in the negative.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper resolves two open problems in extremal set theory. It proves that if F ⊆ 2^[n] is an IU-family (satisfying both the intersecting condition F ∩ F' ≠ ∅ and the union condition F ∪ F' ≠ [n] for all distinct F, F' in F), then the sturdiness β(F) — defined as the minimum of |F(i, ¯j)| over i ≠ j — satisfies β(F) ≤ 2^{n-4}, confirming a conjecture of Frankl and Wang. It also establishes a tight upper bound on the sum of sizes of cross t-intersecting separated families and supplies explicit counterexamples that settle in the negative an open problem posed by Frankl, Liu, Wang and Yang.
Significance. If the results hold, they advance extremal set theory by strengthening the classical IU-Theorem (|F| ≤ 2^{n-2}) with a uniform lower bound on the size of all slices F(i, ¯j), and by extending prior work on separated families with a sharp sum bound together with concrete constructions that falsify the open question. The combinatorial arguments via averaging over pairs and exhaustive case analysis on the slices, together with the explicit counterexamples, constitute verifiable contributions that can be checked directly against the definitions.
minor comments (3)
- [Abstract] The abstract introduces the notation F(i, ¯j) and the IU conditions but does not explicitly restate the precise definition of an IU-family before stating the new bound; adding one sentence would improve readability for readers who consult only the abstract.
- [Section on cross t-intersecting families] The claim that the bound on cross t-intersecting separated families is tight would be strengthened by an explicit reference to the section or construction that achieves equality (e.g., the extremal example for t=1).
- [Introduction] A short remark comparing the new 2^{n-4} bound with the classical 2^{n-2} size bound of the IU-Theorem would clarify the improvement for readers.
Simulated Author's Rebuttal
We thank the referee for the positive report, accurate summary of our two main results, and recommendation of minor revision. We appreciate the recognition that our proofs and counterexamples advance the understanding of IU-families and separated families in extremal set theory.
Circularity Check
No significant circularity detected
full rationale
The paper derives its bounds through direct combinatorial case analysis on the slices F(i,¯j) and averaging arguments that apply the external IU-Theorem bound |F| ≤ 2^{n-2} as an independent input, without reducing the target inequality β(F) ≤ 2^{n-4} to a redefinition or fitted parameter. The second result supplies explicit constructions that falsify the prior open problem by direct verification, extending results from non-overlapping authors. No self-definitional steps, load-bearing self-citations, or ansatz smuggling appear in the derivation chain.
Axiom & Free-Parameter Ledger
axioms (2)
- standard math The power set 2^[n] with the standard subset, intersection, and union operations forms a Boolean lattice.
- domain assumption Every IU-family satisfies both the intersection constraint F ∩ F' ≠ ∅ and the union constraint F ∪ F' ≠ [n] for all distinct F, F'.
Reference graph
Works this paper leans on
-
[1]
Anderson, Intersection theorems and a lemma of Kleitman, Discrete Math
I. Anderson, Intersection theorems and a lemma of Kleitman, Discrete Math. 16 (3) (1976) 181–185
work page 1976
- [2]
-
[3]
P. Erd˝ os, C. Ko, R. Rado, Intersection theorems for systems of finite sets, Q. J. Math. 2 (1961) 313–320
work page 1961
-
[4]
Frankl, The proof of a conjecture of G.O.H
P. Frankl, The proof of a conjecture of G.O.H. Katona, J. Combin. Theory Ser. A 19 (2) (1975) 208–213
work page 1975
-
[5]
Frankl, Antichains of fixed diameter, Mosc
P. Frankl, Antichains of fixed diameter, Mosc. J. Comb. Number Theory 7 (2017) 3–33
work page 2017
-
[6]
Frankl, Maximal degree and diversity in intersecting hypergraphs, J
P. Frankl, Maximal degree and diversity in intersecting hypergraphs, J. Combin. Theory Ser. B 144 (2020) 81–94
work page 2020
- [7]
- [8]
- [9]
- [10]
- [11]
- [12]
- [13]
- [14]
- [15]
-
[16]
Huang, Two extremal problems on intersecting families, European J
H. Huang, Two extremal problems on intersecting families, European J. Combin. 76 (2019) 1–9
work page 2019
-
[17]
Kleitman, Families of non-disjoint subsets, J
D. Kleitman, Families of non-disjoint subsets, J. Combin. Theory 1 (1966) 153–155
work page 1966
-
[18]
Kupavskii, Diversity of uniform intersecting families, European J
A. Kupavskii, Diversity of uniform intersecting families, European J. Combin. 74 (2018) 39–47
work page 2018
- [19]
-
[20]
Liu, The maximum sum of the sizes of cross-intersecting separated families, AIMS Math
E. Liu, The maximum sum of the sizes of cross-intersecting separated families, AIMS Math. 8 (12) (2023) 30910–30921
work page 2023
- [21]
-
[22]
Patk´ os, Size, diversity, minimum degree, sturdiness, d¨ omd¨ od¨ om, (2025), arXiv:2501.02596
B. Patk´ os, Size, diversity, minimum degree, sturdiness, d¨ omd¨ od¨ om, (2025), arXiv:2501.02596
-
[23]
Seymour, On incomparable collections of sets, Mathematika, 20 (1973) 208–209
P. Seymour, On incomparable collections of sets, Mathematika, 20 (1973) 208–209
work page 1973
-
[24]
M. Siggers, N. Tokushige, The maximum size of intersecting and union families of sets, European J. Combin. 33 (2012) 128–138. 11
work page 2012
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.