On $L$-close Sperner systems

Balazs Patkos; Daniel Nagy

On $L$-close Sperner systems

T0 review · 0 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper proves that any family of subsets of an $n$-element set whose pairwise skew distances are confined to a fixed set $L$ of positive integers has at most as many members as the total number of subsets of size at most $|L|$, and…

desk verdict A correct, genuinely new generalization of the BGM 1-close bound to arbitrary singleton skew distances and a Frankl-Wilson type bound for general L; minor typos but sound. read the letter →

arxiv 1908.01744 v3 pith:U4GQ7VQ3 submitted 2019-08-05 math.CO

Daniel Nagy , Balazs Patkos This is my paper · ORCID

classification math.CO MSC 05D0505A20

keywords L-closeSpernerskewdistanceantichainmultilinearpolynomialmethodlinearindependenceextremalsettheorytracefamilies

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper proves a size bound for families of subsets of $[n]$ whose pairwise skew distances all lie in a fixed set $L$ of positive integers: such a family has at most $\sum_{h=0}^{|L|} \binom{n}{h}$ members, and if $L$ is a single integer, at most $n$ members. This recovers and extends the earlier linear-independence bound for 1-close Sperner families and gives a skew-distance analogue of the classical $L$-intersection bound. The proof is a short polynomial method: each set is assigned a multilinear polynomial that vanishes on every other member when the family is ordered by decreasing size, so the polynomials must be linearly independent. The paper also settles the case $L=\{0,1\}$, where comparability is allowed, by proving the exact maximum is $\binom{n}{2}+2n-1$.

What carries the argument

The central object is the multilinear polynomial $p_{F,L}(x)=\prod_{h\in L}(|F|-v_F\cdot x-h)$, obtained from the corresponding ordinary polynomial by replacing every $x_i^t$ with $x_i$. Its key evaluation identity is $p_{F,L}(v_G)=\prod_{h\in L}(|F\setminus G|-h)$, which is nonzero when $F=G$ and zero for every pair with $|F\setminus G|\in L$. Ordering the family by non-increasing size makes the evaluation matrix triangular, so the independence lemma applies and the dimension of the space of multilinear polynomials of degree at most $|L|$ — namely $\sum_{h=0}^{|L|}\binom{n}{h}$ — bounds the family size. For $|L|=1$, the same evaluation identity is combined with a coefficient argument that shows the scaled polynomials cannot express the constant function $1$, giving the stronger $m\leq n$.

What would settle it

Look for a counterexample with $L=\{0\}$: the maximal chain $\emptyset\subset\{1\}\subset\{1,2\}\subset\dots\subset[n]$ has $n+1$ sets and every distinct pair has skew distance $0$, so it violates the $|L|=1$ conclusion $m\leq n$ if $0$ were admitted. This pinpoints the exact spot where the positivity of $L$ is doing the work, since the product $\prod_{h\in L}(-h)$ in the proof is the only obstruction.

Watch

Extended reading notes

Core claim

On its own terms, the paper's discovery is a triangular polynomial separation for skew-distance families: if $\{F_1,\dots,F_m\}$ is $L$-close Sperner with $L\subseteq [n]$ consisting of positive integers, then, listed in non-increasing order of size, the polynomials $p_{F_i,L}$ vanish on the characteristic vectors of earlier sets and not on their own, forcing linear independence. Counting the ambient space of multilinear polynomials of degree at most $|L|$ gives $m \leq \sum_{h=0}^{|L|} \binom{n}{h}$. For a single allowed distance $L=\{s\}$, the same identity shows the polynomials together with the constant polynomial $1$ are independent, so $m\leq n$. When $0$ is allowed, the paper reproves the exact result that a $\{0,1\}$-skew-distance family in $2^{[n]}$ has at most $\binom{n}{2}+2n-1$ members, via an induction that splits the family into two pieces and controls one of them by a chain-like representative argument.

Load-bearing premise

The load-bearing assumption is that every allowed skew distance is a positive integer: the proof needs $p_{F,L}(v_F)=\prod_{h\in L}(-h)$ to be nonzero, and when $0\in L$ the conclusion $m\leq n$ fails, as a chain of length $n+1$ shows.

Editorial extensions

If this is right

For $L=\{1,2,\dots,k\}$ (the $k$-close Sperner property), the bound $m\leq \sum_{h=0}^k \binom{n}{h}$ is asymptotically sharp as $n$ grows, witnessed by the uniform family of all $k$-subsets.
For a single positive skew distance $s$, no such family can have more than $n$ sets; the bound is tight for $s=1$ via all singletons, and for prime-power $s$ via the lines of a projective plane when $n=s^2+s+1$.
The exact maximum size of a $\{0,1\}$-skew-distance family in $2^{[n]}$ is $\binom{n}{2}+2n-1$ for every $n\geq 3$, matching the construction that layers a chain onto a near-uniform family.
Because the bound depends only on $|L|$, families with scattered allowed distances behave like families with a consecutive block of the same length, a direct analogue of the $L$-intersection phenomenon.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The polynomial separator is generic: applying the paper's set-encoding to the $q$-ary poset $Q_n$ produces $L$-close Sperner families in a larger cube, so a linear $O_q(n)$ upper bound for $\{1\}$-close families in $Q_n$ — a conjecture recorded in the paper — would follow from the same dimension argument rather than a bespoke construction.
The observation that $L=\{\ell+1,\dots,n\}$-close Sperner families are exactly $(n-\ell)$-trace Sperner families transfers Theorem 1.2 into an explicit upper bound for trace problems, connecting skew-distance families to a classical invariant.
The $0$-in-$L$ case is structurally different: the exact $\{0,1\}$ value exceeds the positive-integer sum bound, so any full understanding of $ex_{sd}(n,L)$ for $0\in L$ will need new machinery rather than a tweak of the polynomial count.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Zoli,

Short version: this is a correct, useful little paper. The main new result is Theorem 1.2: for L-close Sperner families with L consisting of positive integers, the maximum size is at most sum_{h=0}^{|L|} C(n,h), and when |L|=1 it's at most n. The |L|=1 case generalizes Boros-Gurvich-Milanič's linear independence bound for 1-close Sperner systems to any single skew distance, and it's sharp via singletons and projective planes. The proof is the standard triangularization polynomial method: list sets by decreasing size, define p_{F,L} as the multilinearized product over h in L of (|F| - v_F·x - h), and observe the evaluation matrix is triangular with nonzero diagonal. That part is sound. The |L|=1 moreover part uses a Blokhuis-style argument to include the constant polynomial and rule out dependence; the descending induction on levels works, and the only excluded case is the family {∅}, which is indeed a genuine exception. I checked the algebra on examples; it holds up.

The paper also gives a new proof of the Frankl-Füredi-Pach theorem for {0,1}-skew-distance systems. The proof is inductive and reasonably clean, but it relies on a structural fact that it dismisses as 'an exercise' and cites as Lemma 19 of [5]. For a theorem that's already known, that's a minor self-containedness gap, not a correctness issue.

Soft spots are minor. There are two index typos in the proof of Theorem 2.1: the sentence about vanishing should say 'if |F_i| ≤ |F_j|' and '|F_i \ F_j| ∈ L' and conclude p_{F_i}(v_{F_j}) = 0. As printed, the inequality and subscripts are at least one of those things off, though the intended meaning is clear from context. Fix that before publication. Also, the paper doesn't address L containing 0 for the main theorem, but it explicitly explains why that's not a technicality (chains give n+1 for L={0}), so that's fair.

No data, no fitting, no circularity. The citations are appropriate, including their own work; the self-citations are for context, not to prop up the result. The Q_n conjecture is a nice hook for future work.

Who is this for? People working in extremal set theory, especially the polynomial method. It will not change the field, but it's a solid, citable result with a clean proof. I'd send it to a good combinatorics journal, not desk reject. A serious referee should be able to verify it in an afternoon. Recommend: accept with minor corrections.

Referee Report

0 major / 4 minor

Summary. The paper studies L-close Sperner families in 2^[n], where every pair of distinct sets has skew distance sd(F,G)=min(|F\G|,|G\F|) belonging to a fixed set L of positive integers. Theorem 1.2 bounds such a family by sum_{h=0}^{|L|} C(n,h), and by n when |L|=1. The proof assigns to each set F a multilinear polynomial p_{F,L}, orders the sets by non-increasing size, and uses Lemma 1.3 to conclude linear independence; the |L|=1 case additionally shows that the polynomials remain independent together with the constant polynomial, via a descending induction on set sizes. The paper also gives a new proof of the Frankl-Furedi-Pach theorem exsd(n,{0,1}) = C(n,2)+2n-1 by induction, and closes with remarks on trace-Sperner families and a q-ary generalization.

Significance. If correct, Theorem 1.2 genuinely generalizes the Boros-Gurvich-Milanič result: it gives the linear bound m ≤ n for every single positive skew distance, and a Frankl-Wilson-type bound for arbitrary L. The polynomial proof is elegant and essentially self-contained: Lemma 1.3 is proved, the multilinearization step is valid, and the sign argument for |L|=1 is sound, with the {∅} edge case explicitly handled. The reproof of Theorem 1.4 is a nice additional contribution, though it imports Lemma 19 of [5] rather than proving it in the text. The sharpness examples (all k-subsets for L={1,...,k} and projective planes for L={q}) are appropriate and strengthen the paper.

minor comments (4)

[Proof of Theorem 1.4] The existence of representative sets C_i for uniform levels with |F_i| ≥ 3 is delegated to 'an exercise for the reader (see Lemma 19 in [5])'; since the proof of Theorem 1.4 depends on this structural fact, the authors should either state and prove the needed Johnson-graph clique lemma or give a precise citation with statement.
[Section 2, proof of Theorem 2.1, equation (2)] The identity p_{F',L}(v_F) = |F'|-|F| for |F'|>|F| is terse. The equality is correct because |F'|>|F| implies |F'\F| > |F\F'|, so the min equals |F\F'| = s and hence |F'\F| - s = |F'|-|F|; adding this one-line explanation would improve readability.
[Proof of Theorem 1.4, base case] In the line 'C(3,2)+2·3−1 = 2 3' the displayed value appears garbled: the expression equals 8, which is |2^[3]| and makes the base case trivial. Please correct the typographical rendering.
[Abstract and Introduction] The definition of L-close Sperner is given twice, in the abstract and in the introduction; the later definition of L-sd for sets possibly containing 0 is clear, but a sentence in the introduction explicitly noting that 0 ∉ L is essential for Theorem 1.2 would help prevent the reader from applying the result to L={0}, for which the conclusion fails.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: Theorem 1.2 is derived from first principles via a standard polynomial independence argument.

full rationale

The central new result, Theorem 1.2, is self-contained and not circular. The proof defines multilinearized polynomials p_{F,L} in the space M_{|L|} of dimension sum_{h=0}^{|L|} C(n,h), orders the sets by nonincreasing size, and applies Lemma 1.3: for i > j one has p_{F_i,L}(v_{F_j}) = prod_{h in L}(|F_i \ F_j| - h) = 0 because the L-close Sperner property and the size ordering put |F_i \ F_j| in L, while p_{F_i,L}(v_{F_i}) = prod_{h in L}(-h) != 0 exactly because L contains only positive integers. Thus the upper bound m <= sum C(n,h) is a direct linear-independence bound, not an input disguised as an output. The moreover part for |L| = 1 is proved by a separate descending induction on set size with real coefficients; the bound m <= n follows from linear independence together with the constant polynomial, again by construction rather than by assumption. The reproof of the known Frankl-Furedi-Pach theorem cites Lemma 19 of [5] without proof, but that lemma is attributed to other authors, concerns uniform 1-close Sperner families, and is used only in the secondary reproof, not in the proof of Theorem 1.2. The paper's self-citations are contextual (e.g., the book [11] and the author's own trace-Sperner paper [12]) and are not load-bearing for the main theorem. There are no fitted parameters, no predictions that reduce to inputs, and no uniqueness claims imported from the authors' own prior work. The derivation chain is therefore free of circularity; the unproved external lemma is at most a completeness issue in a supplementary proof, not a circular step.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

No free parameters or invented entities. The central proof for Theorem 1.2 relies only on standard linear algebra, covered by the first two axioms. The reproof of Theorem 1.4 additionally leans on a cited structural lemma, the third axiom.

assumptions (3)

standard math Lemma 1.3: if polynomials p_i and vectors v_i satisfy p_i(v_i) is not 0 and p_i(v_j)=0 for all j<i, then the p_i are linearly independent.
Proved in Section 1; it is the engine of the polynomial-method proof of Theorem 2.1.
standard math Multilinearization x_i^t maps to x_i preserves values on 0-1 vectors, placing p_{F,L} in the space M_{|L|} spanned by multilinear monomials of degree at most |L|.
Used in Section 2 to get the dimension bound dim M_{|L|} = sum_{h=0}^{|L|} C(n,h).
domain assumption Lemma 19 of [5]: in a 1-close Sperner family, any level with at least three sets has a representative set that is either contained in the intersection of all sets on the level or contains their union.
Invoked as an exercise for the reader in Section 2 before Claim 2.2; the induction proof of Theorem 1.4 depends on it and it is not proved in this paper.

how reviews work

0 comments

Cite this review

Pith. "Pith review of On $L$-close Sperner systems." pith.science (2026). https://pith.science/paper/U4GQ7VQ3

@misc{pith2026190801744,
  author       = {Pith},
  title        = {Pith review of: On $L$-close Sperner systems},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/U4GQ7VQ3}},
  note         = {Machine review of arXiv:1908.01744}
}

abstract

For a set $L$ of positive integers, a set system $\mathcal{F} \subseteq 2^{[n]}$ is said to be $L$-close Sperner, if for any pair $F,G$ of distinct sets in $\mathcal{F}$ the skew distance $sd(F,G)=\min\{|F\setminus G|,|G\setminus F|\}$ belongs to $L$. We reprove an extremal result of Boros, Gurvich, and Milani\v c on the maximum size of $L$-close Sperner set systems for $L=\{1\}$ and generalize to $|L|=1$ and obtain slightly weaker bounds for arbitrary $L$. We also consider the problem when $L$ might include 0 and reprove a theorem of Frankl, F\"uredi, and Pach on the size of largest set systems with all skew distances belonging to $L=\{0,1\}$.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

13 extracted references · 13 canonical work pages

[5]

Boros, V

E. Boros, V. Gurvich, M. Milaniˇ c, Decomposing 1-Sperner hype rgraphs. Electron. J. Com- bin. 26 (3) (2019), P3.18

work page 2019
[1]

N. Alon, L. Babai, M. Suzuki, Multilinear polynomials and Frankl-Ray- Chaudhuri-Wilson type intersection theorems. Journal of Combinatorial Theory, S eries A, 58(2) (1991), 165– 180

work page 1991
[2]

Babai, P

L. Babai, P. Frankl, Linear Algebra Methods in Combinatorics: With Application s to Ge- ometry and Computer Science . Department of Computer Science, University of Chicago 1992

work page 1992
[3]

Blokhuis, A new upper bound for the cardinality of 2-distance s ets in Euclidean space, Ann

A. Blokhuis, A new upper bound for the cardinality of 2-distance s ets in Euclidean space, Ann. Discrete Math. 20 (1984), 65–66

work page 1984
[4]

Characterizing and decomposing classes of threshold, split, and bipartite graphs via 1-Sperner hypergraphs

E. Boros, V. Gurvich, M. Milaniˇ c, Characterizing and decompos ing classes of threshold, split, and bipartite graphs via 1-Sperner hypergraphs. to appear in Journal of Graph Theory, doi: 10.1002/jgt.22529, arXiv:1805.03405

work page Pith review arXiv
[6]

Chiarelli, M

N. Chiarelli, M. Milaniˇ c, Linear separation of connected dominating sets in graphs.Ars Math. Contemp., 16 (2019), 487–525

work page 2019
[7]

Engel, Sperner theory

K. Engel, Sperner theory. Vol. 65. Cambridge University Press, 1997. 7

work page 1997
[8]

Erd˝ os, C

P. Erd˝ os, C. Ko, R. Rado, Intersection theorems for system s of ﬁnite sets, Quart. J. Math. Oxford Ser. 12 (1961), 313–320

work page 1961

Show all 13 references

[9]

Frankl, Z

P. Frankl, Z. F¨ uredi, J. Pach, Bounding one-way diﬀerences, G raphs and Combinatorics 3(1) (1987) 341–347

1987
[10]

Frankl, R.M

P. Frankl, R.M. Wilson, Intersection theorems with geometric co nsequences, Combinatorica 1 (1981), 357–368

1981
[11]

Gerbner, B

D. Gerbner, B. Patk´ os, Extremal Finite Set Theory . CRC Press. 2018

2018
[12]

Patk´ os,l-trace k-Sperner families, J

B. Patk´ os,l-trace k-Sperner families, J. Combin. Theory Ser. A 116 (2009), 1047–105 5

2009
[13]

Sperner, Ein Satz ¨ uber Untermengen einer endlichen Menge, Math

E. Sperner, Ein Satz ¨ uber Untermengen einer endlichen Menge, Math. Z. 27 (1928), 544–548. 8

1928

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [5]

Boros, V

E. Boros, V. Gurvich, M. Milaniˇ c, Decomposing 1-Sperner hype rgraphs. Electron. J. Com- bin. 26 (3) (2019), P3.18

work page 2019

[2] [1]

N. Alon, L. Babai, M. Suzuki, Multilinear polynomials and Frankl-Ray- Chaudhuri-Wilson type intersection theorems. Journal of Combinatorial Theory, S eries A, 58(2) (1991), 165– 180

work page 1991

[3] [2]

Babai, P

L. Babai, P. Frankl, Linear Algebra Methods in Combinatorics: With Application s to Ge- ometry and Computer Science . Department of Computer Science, University of Chicago 1992

work page 1992

[4] [3]

Blokhuis, A new upper bound for the cardinality of 2-distance s ets in Euclidean space, Ann

A. Blokhuis, A new upper bound for the cardinality of 2-distance s ets in Euclidean space, Ann. Discrete Math. 20 (1984), 65–66

work page 1984

[5] [4]

Characterizing and decomposing classes of threshold, split, and bipartite graphs via 1-Sperner hypergraphs

E. Boros, V. Gurvich, M. Milaniˇ c, Characterizing and decompos ing classes of threshold, split, and bipartite graphs via 1-Sperner hypergraphs. to appear in Journal of Graph Theory, doi: 10.1002/jgt.22529, arXiv:1805.03405

work page Pith review arXiv

[6] [6]

Chiarelli, M

N. Chiarelli, M. Milaniˇ c, Linear separation of connected dominating sets in graphs.Ars Math. Contemp., 16 (2019), 487–525

work page 2019

[7] [7]

Engel, Sperner theory

K. Engel, Sperner theory. Vol. 65. Cambridge University Press, 1997. 7

work page 1997

[8] [8]

Erd˝ os, C

P. Erd˝ os, C. Ko, R. Rado, Intersection theorems for system s of ﬁnite sets, Quart. J. Math. Oxford Ser. 12 (1961), 313–320

work page 1961