Improved bound on symmetric differences of intersecting families

Lihua Feng; Qifan Wang; Yongjiang Wu

arxiv: 2606.20043 · v1 · pith:4HE4AWD3new · submitted 2026-06-18 · 🧮 math.CO

Improved bound on symmetric differences of intersecting families

Qifan Wang , Yongjiang Wu , Lihua Feng This is my paper

Pith reviewed 2026-06-26 17:05 UTC · model grok-4.3

classification 🧮 math.CO MSC 05D05

keywords intersecting familiessymmetric differencesuniform set familiesextremal set theoryconcentration inequalitiesbinomial coefficients

0 comments

The pith

Any intersecting family of k-subsets satisfies |SD(F)| ≤ sum_{ℓ=0}^{k-1} binom(n-1,2ℓ) when n ≥ 60 k^{3/2} and k ≥ 50, with equality only for stars.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves an upper bound on the number of distinct symmetric differences that can arise from an intersecting family of k-element subsets. The bound states that this number cannot exceed the sum of the binomial coefficients binom(n-1,2ℓ) for ℓ from 0 to k-1, provided the ground set is large enough relative to k. This confirms a recent conjecture in the stated parameter range and pins down the families that achieve the maximum as stars, meaning all sets contain one fixed element. A reader would care because the result shows how the intersecting property restricts the variety of pairwise symmetric differences in a concrete numerical way. The argument relies on applying a concentration inequality to control the sizes that appear in the symmetric difference family.

Core claim

For any intersecting family F ⊆ binom([n],k) with n ≥ 60k^{3/2} and k ≥ 50, |SD(F)| ≤ sum_{ℓ=0}^{k-1} binom(n-1,2ℓ), and the only extremal families are stars.

What carries the argument

A concentration inequality applied to the distribution of symmetric differences within an intersecting family, which controls how many distinct even-sized sets can appear.

If this is right

The 2023 conjecture holds throughout the regime n ≥ 60 k^{3/2} for k ≥ 50.
Stars are the unique families attaining the maximum number of symmetric differences.
The same concentration method yields the bound directly once n is large enough relative to k.
Previous arguments that required n > 3k^2 are improved to a weaker growth condition on n.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same concentration technique might close the remaining gap down to n > 10k if the constants can be sharpened.
One could test whether non-star families exceed the bound for moderate k just below the 60 k^{3/2} threshold.
Analogous size bounds on symmetric differences may hold for t-intersecting families with adjusted right-hand sides.

Load-bearing premise

The ground set size n must be at least 60 times k to the power three-halves so that the concentration inequality produces a bound tight enough to match the star size.

What would settle it

Exhibit an intersecting family on n = 59 k^{3/2} elements with k = 50 where the number of distinct symmetric differences exceeds the stated sum, or show a non-star family achieving equality inside the stated range.

read the original abstract

For a family $\mathcal{F}$, it is called intersecting if $F\cap F'\neq \emptyset$ for all $F,F'\in\mathcal{F}$. We use $\mathcal{SD}(\mathcal{F}) = \{F \triangle G : F, G \in \mathcal{F}\}$ to denote the family of symmetric differences of $\mathcal{F}$. In 2023, Frankl, Kiselev and Kupavskii conjectured that for any intersecting family $\mathcal{F} \subseteq \binom{[n]}{k}$ with $n > 10k$, the inequality $|\mathcal{SD}(\mathcal{F})| \le \sum_{\ell=0}^{k-1} \binom{n-1}{2\ell}$ holds. They further observed that a proof for the range $n>3k^2$ could likely be obtained via arguments similar to those in their earlier work, though no detailed derivation was given. In this paper, we establish the conjecture under the conditions $n\ge 60k^{3/2}$ and $k\ge 50$. We also determine the extremal families, which are precisely a certain class of stars. A concentration inequality plays a central role in the proof.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper proves the 2023 Frankl-Kiselev-Kupavskii conjecture on symmetric differences of intersecting k-uniform families, but only for n ≥ 60k^{3/2} and k ≥ 50 via concentration inequalities.

read the letter

The key takeaway is that Wang, Wu, and Feng establish the conjecture for intersecting families F in the binomial coefficient of [n] choose k when n is at least 60 times k to the three-halves and k at least 50. They show |SD(F)| is at most the sum from ell=0 to k-1 of binomial(n-1, 2ell), with equality only for stars. This is the first proof in that regime.

The new part is turning the earlier observation about n > 3k squared into an actual argument using a concentration inequality to bound how the symmetric differences distribute. They also pin down the extremal examples cleanly. The approach stays within standard combinatorial facts plus one external inequality, so there is no obvious circularity or invented machinery.

The main limitation is the range itself. The conjecture asked for n > 10k, and this is a stricter polynomial threshold. That leaves the gap between 10k and 60k^{3/2} open, and the k ≥ 50 cutoff is a technical detail that might shrink later but is not the central issue. The abstract is explicit about these restrictions, so the claim matches what is delivered.

The paper is aimed at people working on intersecting families and variants of the Erdős–Ko–Rado theorem. Anyone tracking progress on the 2023 conjecture will want to see the details. The argument is grounded enough and the result is a concrete step forward, so it should go to peer review rather than a desk reject.

Referee Report

0 major / 2 minor

Summary. The manuscript proves the Frankl-Kiselev-Kupavskii conjecture for intersecting k-uniform families F ⊆ binom([n],k) under the conditions n ≥ 60k^{3/2} and k ≥ 50: |SD(F)| ≤ ∑_{ℓ=0}^{k-1} binom(n-1,2ℓ), with equality only for a certain class of stars. The argument applies a concentration inequality to bound the distribution of symmetric differences and deduces both the size bound and the extremal characterization.

Significance. If the derivation holds, the result establishes the conjecture in the regime n = Ω(k^{3/2}), which is weaker than the conjectured n > 10k but stronger than the n > 3k^2 regime previously indicated as accessible by similar methods. The explicit identification of extremal examples and the use of a standard concentration tool constitute a concrete advance toward the full conjecture.

minor comments (2)

The abstract and introduction should state the precise form of the concentration inequality invoked (including any tail bounds or variance assumptions) and indicate where in the proof the condition n ≥ 60k^{3/2} is derived from those parameters.
Verify that the error terms arising from the concentration step remain negligible uniformly for all pairs F,G when k = 50 and n is at the lower threshold 60k^{3/2}; a short explicit calculation or reference to the relevant lemma would clarify this.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript, accurate summary of the main result, and recommendation of minor revision. The significance statement correctly positions the new range n = Ω(k^{3/2}) relative to the conjecture and prior work.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper proves a conditional version of an external conjecture (Frankl-Kiselev-Kupavskii) by applying a standard concentration inequality to bound symmetric differences in intersecting families, under explicitly stated parameter restrictions n ≥ 60k^{3/2} and k ≥ 50. The derivation relies on external combinatorial facts and the concentration tool rather than any self-definition, fitted-parameter renaming, or load-bearing self-citation chain. No equation or step reduces the claimed bound to its own inputs by construction, and the extremal characterization follows from the same external tools. The result is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The proof rests on standard mathematical facts about intersecting families and binomial coefficients together with the applicability of a concentration inequality in the stated regime; no free parameters, new entities, or ad-hoc axioms are introduced.

axioms (2)

standard math Standard properties of intersecting families and symmetric differences in the Boolean lattice
Invoked throughout the argument as background.
domain assumption The chosen concentration inequality applies with sufficient strength when n ≥ 60k^{3/2} and k ≥ 50
Central to obtaining the bound, as highlighted in the abstract.

pith-pipeline@v0.9.1-grok · 5745 in / 1354 out tokens · 34522 ms · 2026-06-26T17:05:36.935446+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

12 extracted references

[1]

Erd˝ os, C

P. Erd˝ os, C. Ko, R. Rado, Intersection theorems for systems of finite sets, Q. J. Math. Oxford 2 (1961) 313–320

1961
[2]

Frankl, On the number of distinct differences in an intersecting family, Discrete Math

P. Frankl, On the number of distinct differences in an intersecting family, Discrete Math. 34 (2021) 112210

2021
[3]

Frankl, S

P. Frankl, S. Kiselev, A. Kupavskii, On the maximum number of distinct intersections in an intersecting family, Discrete Math. 345 (2022) 112757

2022
[4]

Frankl, S

P. Frankl, S. Kiselev, A. Kupavskii, Best possible bounds on the number of distinct differences in intersecting families, European J. Combin. 107 (2023) 103601. 10

2023
[5]

Frankl, J

P. Frankl, J. Wang, Intersections and distinct intersections in cross-intersecting fam- ilies, European J. Combin. 110 (2023) 103665

2023
[6]

Frankl, J

P. Frankl, J. Wang, Improved bounds on the maximum diversity of intersecting families, European J. Combin. 118 (2024) 103885

2024
[7]

Katona, Intersection theorems for systems of finite sets, Acta Math

G. Katona, Intersection theorems for systems of finite sets, Acta Math. Acad. Sci. Hungar. 15 (1964) 329–337

1964
[8]

Katona, A theorem of finite sets, in: Theory of Graphs, Proc

G. Katona, A theorem of finite sets, in: Theory of Graphs, Proc. Colloq. Tihany, Akad. Kiad´ o, Budapest, 1966, pp. 187–206

1966
[9]

Kruskal, The number of simplices in a complex, in: Math

J. Kruskal, The number of simplices in a complex, in: Math. Optimization Tech- niques, Univ. of Calif. Press, Berkeley, 1963, pp. 251–278

1963
[10]

Lov´ asz, Combinatorial Problems and Exercises, 13.31, Akad

L. Lov´ asz, Combinatorial Problems and Exercises, 13.31, Akad. Kiad´ o, Budapest, North-Holland, Amsterdam, 1979

1979
[11]

Lemons, C

N. Lemons, C. Palmer, Unbalance of set systems, Graphs Combin. 24 (2008) 361–365

2008
[12]

Marica, J

J. Marica, J. Sch¨ onheim, Differences of sets and a problem of graham, Canad. Math. Bull. 12 (1969) 635–637. 11

1969

[1] [1]

Erd˝ os, C

P. Erd˝ os, C. Ko, R. Rado, Intersection theorems for systems of finite sets, Q. J. Math. Oxford 2 (1961) 313–320

1961

[2] [2]

Frankl, On the number of distinct differences in an intersecting family, Discrete Math

P. Frankl, On the number of distinct differences in an intersecting family, Discrete Math. 34 (2021) 112210

2021

[3] [3]

Frankl, S

P. Frankl, S. Kiselev, A. Kupavskii, On the maximum number of distinct intersections in an intersecting family, Discrete Math. 345 (2022) 112757

2022

[4] [4]

Frankl, S

P. Frankl, S. Kiselev, A. Kupavskii, Best possible bounds on the number of distinct differences in intersecting families, European J. Combin. 107 (2023) 103601. 10

2023

[5] [5]

Frankl, J

P. Frankl, J. Wang, Intersections and distinct intersections in cross-intersecting fam- ilies, European J. Combin. 110 (2023) 103665

2023

[6] [6]

Frankl, J

P. Frankl, J. Wang, Improved bounds on the maximum diversity of intersecting families, European J. Combin. 118 (2024) 103885

2024

[7] [7]

Katona, Intersection theorems for systems of finite sets, Acta Math

G. Katona, Intersection theorems for systems of finite sets, Acta Math. Acad. Sci. Hungar. 15 (1964) 329–337

1964

[8] [8]

Katona, A theorem of finite sets, in: Theory of Graphs, Proc

G. Katona, A theorem of finite sets, in: Theory of Graphs, Proc. Colloq. Tihany, Akad. Kiad´ o, Budapest, 1966, pp. 187–206

1966

[9] [9]

Kruskal, The number of simplices in a complex, in: Math

J. Kruskal, The number of simplices in a complex, in: Math. Optimization Tech- niques, Univ. of Calif. Press, Berkeley, 1963, pp. 251–278

1963

[10] [10]

Lov´ asz, Combinatorial Problems and Exercises, 13.31, Akad

L. Lov´ asz, Combinatorial Problems and Exercises, 13.31, Akad. Kiad´ o, Budapest, North-Holland, Amsterdam, 1979

1979

[11] [11]

Lemons, C

N. Lemons, C. Palmer, Unbalance of set systems, Graphs Combin. 24 (2008) 361–365

2008

[12] [12]

Marica, J

J. Marica, J. Sch¨ onheim, Differences of sets and a problem of graham, Canad. Math. Bull. 12 (1969) 635–637. 11

1969