A conjecture of Frankl proposed in the 1980s states that for n≥2d, every Sperner family F⊆2[n] of VC-dimension at most d has at most (dn) members. We prove this conjecture for every fixed d and large n, and show that equality holds only when F is (d[n]) or (n−d[n]).
Introduction
For a finite set V, write (kV)={A⊆V:∣A∣=k} and (≤kV)=⋃j=0k(jV), and set [n]={1,…,n}. We call (kV) the complete layer of sets of size k. A family F⊆2[n] is a Sperner family if no member contains another. Determining the largest possible size of such a family is one of the earliest problems in extremal set theory. Sperner’s theorem [20] states that ∣F∣≤(⌊n/2⌋n), which is sharp.
For S⊆[n], the trace of F on S is F∣S={A∩S:A∈F}. We say that FshattersS if F∣S=2S, and write Sh(F) for the family of shattered sets. The Vapnik–Chervonenkis dimension (VC-dimension for short), denoted by VCdim(F), is the largest size of a shattered set. The Sauer–Shelah lemma [18, 19, 23] states that every family with VCdim(F)≤d satisfies ∣F∣≤∑i=0d(in). This bound can be attained by (≤d[n]). VC-dimension has been studied in several problems in extremal combinatorics. For uniform families, Frankl and Pach [9] proved that a family of sets of size d+1 with VC-dimension at most d has size at most (dn) when n≥2d. Subsequent work has given improved upper bounds and new constructions [1, 4, 12, 15, 22, 24, 25, 26]. Bounded VC-dimension also plays a role in sunflower problems [3, 7, 11] and in graph and Ramsey problems [5, 6, 13, 14, 16, 21].
Notice that for n≥2d, the complete layers (d[n]) and (n−d[n]) are Sperner families of VC-dimension d, each of size (dn). In 1989, Frankl [8] conjectured that these layers have the largest possible size.
Conjecture 1.1. Let d≥1 and n≥2d be integers, and let F⊆2[n] be a Sperner family with VCdim(F)≤d. Then ∣F∣≤(dn).
This conjecture brings together Sperner’s theorem and the Sauer–Shelah lemma. When n=2d or n=2d+1, the proposed bound is exactly the bound in Sperner’s theorem. Frankl [8] proved the cases d=1,2, and Anstee and Sali [2] proved the case d=3. Despite subsequent progress on related problems, the cases of Conjecture 1.1 known in the full range n≥2d have remained d≤3 since 1997. The conjecture was also restated in recent work of Frankl and Wang [10 Conjecture 4.8], Yang and Yu [25 Conjecture 4.4] and Wang, Xu and Zhang [24 Conjecture 3.1].
We prove the conjecture for every fixed d≥3 and large n, and determine the extremal families.
Theorem 1.2. For every integer d≥3, there exists some n0=n0(d) such that for every n>n0, every Sperner family F⊆2[n] with VCdim(F)≤d satisfies ∣F∣≤(dn). Equality holds if and only if F=(d[n]) or F=(n−d[n]).
Remark 1.3. Our proof shows that it suffices to take n0(d)=d10⋅25d−10. The main remaining problem is to establish the conjecture in the full range n≥2d.
Frankl [8] provided the general upper bound (dn)+(d−3n)+(d−6n)+⋯ by a recursive argument and therefore proved the cases d≤2. Anstee and Sali [2] settled d=3 using induction and a characterization of the extremal families for d=1,2. Our proof mainly combines averaging over restrictions, a counting argument based on the ballot problem in the field of enumerative combinatorics [17], and the Sauer-Shelah lemma [18, 19, 23].
Proof of the main theorem
Some useful tools
We write A△B=(A∖B)∪(B∖A) for the symmetric difference of two sets. We first recall two fundamental results related to the main topic of this paper.
Lemma 2.1 ([20]). Every Sperner familyA⊆2[n]satisfies∣A∣≤(⌊n/2⌋n).
Lemma 2.2 ([18, 19, 23]). Letd≥1be an integer andH⊆2[n]be a set system with VC-dimension at mostd. Then∣H∣≤∑j=0d(jn).
We also use the result on the ballot problem in enumerative combinatorics [17].
Lemma 2.3 ([17]). Consider an election with two candidatesAandBwhereAreceivesavotes andBreceivesbvotes, witha≥b. Assume that all voting histories are equally likely. The probability that candidateAis never behind candidateBisa+1a+1−b.
Transformation of the problem and the proof of Theorem 1.2
Let F⊆2[n] be a Sperner family with VCdim(F)≤d. For J⊆[n] and U⊆[n]∖J, define the restricted family FJ,U={A⊆J:A∪U∈F}. We use this notation for any family on a specified ground set. Every restricted family FJ,U is Sperner. For fixed J, each F∈F has a unique decomposition F=A∪U with A⊆J and U⊆[n]∖J. Therefore, ∑U⊆[n]∖J∣FJ,U∣=∣F∣.
Further, for any S⊆J⊆[n], define the family RJ,S={U⊆[n]∖J:S∈Sh(FJ,U)}. We show that any set shattered by RJ,S can be joined to S to give a set shattered by F.
Lemma 2.4. If T∈Sh(RJ,S), then S∪T∈Sh(F). In particular, VCdim(RJ,S)≤d−∣S∣ when ∣S∣≤d, and RJ,S=∅ when ∣S∣>d.
Proof of Lemma 2.4. Note T∈Sh(RJ,S) if and only if for any X⊆T, there exists U∈RJ,S such that U∩T=X. By the definition of RJ,S, U∈RJ,S if and only if S∈Sh(FJ,U). Then for any Y⊆S, there exists A∈F, such that (A∖U)∈FJ,U and (A∖U)∩S=Y. So A∩(S∪T)=X∪Y, which means F shatters S∪T. Note S is disjoint with T, so VCdim(RJ,S)≤d−∣S∣ when ∣S∣≤d. If RJ,S is nonempty and ∣S∣>d, then the empty set can be shattered by RJ,S and hence S can be shattered by F. This contradicts VCdim(F)≤d. □
By Lemma 2.4 and Lemma 2.2, we have ∣RJ,S∣≤∑j=0d−∣S∣(jn−∣J∣). It is not hard to show that for any family A on the finite ground set, ∣A∣≤∣Sh(A)∣. Indeed, we can prove it by using the downshift argument in Lemma 2.9. Also note ∣F∣=∑U⊆[n]∖J∣FJ,U∣. So we have
However, ∑s=0min(∣J∣,d)(s∣J∣)∑j=0d−s(jn−∣J∣)=∑k=0d∑s=0min(∣J∣,k)(s∣J∣)(k−sn−∣J∣)=∑k=0d(kn). Thus this gives the original Sauer–Shelah bound. Splitting the coordinates and counting all shattered sets in this way does not yet improve the bound.
To get the desired bound (dn), we assign the same nonnegative weight ws to every set of size s in J. In other words, we want to have the identity ∑s=0min(∣J∣,d)(s∣J∣)ws∑j=0d−s(jn−∣J∣)=(dn). That is, ∑j=0d(jn−∣J∣)∑s=0min(∣J∣,d−j)(s∣J∣)ws=∑j=0d(jn−∣J∣)(d−j∣J∣). So we can choose the weights so that ∑s=0min(∣J∣,k)(s∣J∣)ws=(k∣J∣) for every 0≤k≤d. With such weights, we have ∣J∣≥2d−1 since ws is nonnegative for every 0≤s≤d.
Put bp,k=(kp)−(k−1p) for integer p>0 and integer 0≤k≤⌊p/2⌋. If we take ∣J∣=2d−1, then we have the following identity.
Lemma 2.5. For every integer n≥2d−1, we have
s=0∑d−1b2d−1,sj=0∑d−s(jn−2d+1)=(dn).
Proof of Lemma 2.5. Note we have ∑s=0d−1b2d−1,s∑j=0d−s(jn−2d+1)=∑j=0d(jn−2d+1)∑s=0min(d−j,d−1)b2d−1,s and ∑s=0ab2d−1,s=(a2d−1) for any 0≤a≤d−1. Since (d−12d−1)=(d2d−1), we have ∑s=0min(d−j,d−1)b2d−1,s=(d−j2d−1) for any 0≤j≤d. So we have
An important observation is that bp,k is related to the ballot problem. For any J⊆[n] of odd size p≥3, let π=(x1,…,xp) be an ordering of J. The set {xs1,…,xsk} with 1≤s1<⋯<sk≤p is called a ballot set if sj≥2j for every j∈[k]. We denote Bp(π) for the family of ballot sets, including the empty set. Every member of Bp(π) has size at most 2p−1.
Lemma 2.6. For 0≤k≤2p−1, there are exactly bp,k members of Bp(π) having size k. If S∈(kJ) and π is chosen uniformly at random, then P(S∈Bp(π))=bp,k/(kp). If ∣J∣=2d−1, then for any ordering π of J, we have
S∈B2d−1(π)∑∣RJ,S∣≤(dn).
Proof of Lemma 2.6. We can see S as a subset of [p] of size k if we see J as [p]. For a fixed subset S of size k, we call an element in [p] selected if S contains this element, and unselected otherwise. Then by the definition of Bp(π), a nonempty subset of J is contained in Bp(π) if and only if the unselected element is never behind the selected element. By Lemma 2.3, we have ∣Bp(π)∩(kJ)∣=p−k+1p−2k+1(kp)=bp,k and P(S∈Bp(π))=bp,k/(kp) when the orderings are uniformly distributed.
Now suppose ∣J∣=2d−1. Then for any ordering π of J, by Lemma 2.2, we have
For any J⊆[n] with ∣J∣=2d−1 and any ordering π of J, by the definition of RJ,S, Lemma 2.6 and double counting the pairs (U,S) with U⊆[n]∖J and S∈Sh(FJ,U)∩B2d−1(π), we have
For any A⊆2J with J⊆[n] having odd size p≥3 and any ordering π of J, we define δp,π(A)=∣Sh(A)∩Bp(π)∣−∣A∣ and δˉp(A)=Eπδp,π(A), where all p! orderings of J are chosen uniformly. Lemma 2.6 gives
We can also average over all J∈(p[n]). Therefore for odd 3≤p≤n, we define
αp(F)=(pn)1J∈(p[n])∑U⊆[n]∖J∑δˉp(FJ,U).(3)
Averaging (1) over all J∈(2d−1[n]) and all orderings π of J, and using (2) and (3), we know that to prove ∣F∣≤(dn), it is enough to show that α2d−1(F)≥0. Indeed, we could also determine all families attaining equality via our approach.
A family on a specified finite set J is called elementary if it is empty, consists of one set, or equals (sJ) for some 0≤s≤∣J∣. We call all other families exceptional. For A⊆2J with ∣J∣=p, put ep(A)=0 if A is elementary and ep(A)=1 otherwise. In particular, A⊊(sJ) is exceptional whenever ∣A∣≥2. Corresponding to (3), for odd 3≤p≤n, we also define
βp(F)=(pn)1J∈(p[n])∑U⊆[n]∖J∑ep(FJ,U).(4)
Note the complete layer (d[n]) attains the desired bound (dn), and every nonempty restricted family of the complete layer (d[n]) must be a complete layer. Therefore we will show β2d−1(F)=0 when α2d−1(F)=0.
For the fixed family F, write αp=αp(F) and βp=βp(F). However, it is hard to prove α2d−1≥0 directly. Therefore, we will firstly prove α3≥0 and β3≤3α3 in Lemma 2.7. Starting from $\alpha_3\geq0 and β3≤3α3, we repeatedly lift J by two coordinates to prove αq≥0 and βq≤Mqαq for every odd 5≤q≤2d−1 when n is sufficiently large in terms of d. Here Mq is a positive number only depending on q when n and d are both fixed. We will show that Mq can be chosen as (q−3)62q−16 in Proposition 2.18.
We firstly prove that for every ordering π, δp,π vanishes on every elementary family. On three coordinates, δ3 is strictly positive for every exceptional Sperner family.
Lemma 2.7.Every elementary family A on a ground set J of odd size p≥3 satisfies δp,π(A)=0 for every ordering π of J, and hence δp(A)=0. Every Sperner family A on a three-element ground set satisfies δ3(A)≥0 and e3(A)≤3δ3(A).
Proof of Lemma 2.7. Recall that δp,π(A)=∣Sh(A)∩Bp(π)∣−∣A∣ and δp(A)=Eπδp,π(A). If A is the empty family, then δp,π(A)=0 for any ordering π since the empty family can not shatter any set. If A is a family consisting of only one set, then A can only shatter the empty set. Hence δp(A)=0 for these two cases.
Now we suppose A is a complete s layer with 1≤s≤p. Then A⊆J is shattered by A if and only if ∣A∣≤min(s,p−s). In fact, the empty trace needs A to have a set disjoint with A, and the full trace needs A to have a set containing A. So ∣A∣≤s and ∣A∣≤p−s. Conversely, suppose ∣A∣≤min(s,p−s). For any subset of A, we can add some elements in J∖A to this subset to get a set of size s. Hence by Lemma 2.6, we have ∣Sh(A)∩Bp(π)∣=∑k=0min(s,p−s)bp,k=(sp)=∣A∣ for every ordering π. So δp(A)=0 if A is a complete layer.
Now we suppose A is a Sperner family on a ground set J with ∣J∣=3. If A is exceptional, then ∣A∣ must be 2 since A is a Sperner family. If A is contained in a complete 1 layer, then A can only shatter the empty set and the sets contained in A. Note b3,0=1 and b3,1=2. Then by (2), we have δ3(A)=31. In the same way, if A is contained in a complete 2 layer, then δ3(A)=31. If A consists of one singleton and one two-element set, then these two sets must be disjoint since A is Sperner. Then A can shatter the empty set and all singletons. So δ3(A)=1. If A is elementary, then e3(A)=0 and δ3(A)=0. Hence δ3(A)≥0 and e3(A)≤3δ3(A) for any Sperner family A on a three-element ground set. □
We now lift J by two coordinates. Ideally, we would like to get αr≤αr+2, but this does not hold in general. The possible loss comes from the fact that adding a subset of the two extra coordinates to a ballot set still gives a ballot set, unless it already has the largest allowed size and both extra coordinates are added. The following inequality describes this possible loss.
For disjoint finite sets J,W and orderings π of J and ρ of W, let πρ denote the ordering of J∪W obtained by listing the elements of J in the order π, followed by the elements of W in the order ρ.
Lemma 2.8.Let r=2t+1≥3 and K=J∪W, where J∩W=∅, ∣J∣=r and ∣W∣=2. Fix orderings π of J and ρ of W. For A⊆2K, put RS(A)={T⊆W:S∈Sh(AJ,T)} for S⊆J. Then
Proof of Lemma 2.8. As in the proof of Lemma 2.4, if we fix S⊆J, then for any T∈Sh(RS(A)), we have S∪T∈Sh(A). Now we fix S∈Br(π) with ∣S∣=k, where 0≤k≤t. If k<t, then for any T⊆W, we have S∪T∈Br+2(πρ), since r+1≥2(k+1) and r+2≥2(k+2). In the same way, if k=t and T⊊W, we also have S∪T∈Br+2(πρ). So we have
Note that for any R⊆2W, we have ∣Sh(R)∣≥∣R∣ and ∣Sh(R)∩{T⊆W:∣T∣≤1}∣ is at least ∣R∣−1{R=2W}. Here 1 is the characteristic function: 1{R=2W}=1 if and only if R=2W, and 1{R=2W}=0 otherwise. So we have
Now we will average the inequality in Lemma 2.8 to show the inequality between αr and αr+2. Before this, we need some lemma to handle the error term {S∈Br(π):∣S∣=t,RS(A)=2W}.
Let H⊆2[m] and i∈[m]. For each H∈H, define
H↓i={H∖{i},H,if i∈H and H∖{i}∈/H,otherwise.
The downshift of H at coordinate i is the family H↓i={H↓i:H∈H}. A coordinate square is Q(B,W)={B∪T:T⊆W}, where ∣W∣=2 and B∩W=∅. We write c2(H) for the number of pairs (B,W) such that Q(B,W)⊆H.
The following lemma bounds the number of coordinate squares.
Lemma 2.9. Let a≥1 be an integer and H⊆2[m] be a set system with VC-dimension at most $a. Then c2(H)≤(2a)∣H∣.
Proof of Lemma 2.9. By the definition of downshift, we know ∣H∣=∣H↓i∣. Now suppose S∈Sh(H↓i). If i∈S, then for any T⊆S∖{i}, we have H∈H↓i such that H∩S=T∪{i}. By the definition of downshift, we know H and H∖{i} are both contained in H, which means H shatters S. If i∈/S, then for any T⊆S, we have H∈H↓i such that H∩S=T. H shatters S since at least one of H∖{i} and H∪{i} is contained in H. So Sh(H↓i)⊆Sh(H).
Claim 2.10. A coordinate downshift does not decrease the number of coordinate squares.
Proof of claim. If a coordinate square Q(B,W) with W={i,j} is contained in H, then Q(B,W) is contained in H↓i after the downshifting of H at i. Now we suppose i∈/B∪W. If both Q(B,W) and Q(B∪{i},W) are contained in H, then any member in Q(B∪{i},W) cannot delete i since Q(B,W) is contained in H. If only one of the Q(B,W) and Q(B∪{i},W) is contained in H, then we have Q(B,W)⊆H↓i. In fact, if Q(B∪{i},W)⊆H and Q(B,W)⊆H, then any member in Q(B,W) but not in H can be obtained after the downshifting of H at i. The other case is obvious. Note every coordinate square with i∈/W belongs to exactly one such pair, so the number of coordinate squares cannot decrease after downshifting. ▪
Note if A contains i and belongs to H↓i, then we can not delete i in A since A∖{i} is already in H↓i. So after the downshifting of H at i, we can not delete i in any set containing i. Moreover, a downshift at another coordinate preserves this property. Let C be the family obtained by downshifting H at each coordinate once for any ordering. So we can not delete any coordinate in C. We also have ∣C∣=∣H∣ and Sh(C)⊆Sh(H). Any set in C can be shattered by C since every subset of this set is already contained in C. So any set in C has size at most a. Note a coordinate square Q(B,W) is contained in C if and only if B∪W is contained in C. Hence by Claim 2.10, we have
c2(H)≤c2(C)=A∈C∑(2∣A∣)≤(2a)∣C∣=(2a)∣H∣.
Suppose that ∣J∣=2t+1 and ∣S∣=t. We will show that if U belongs to a coordinate square in RJ,S, then FJ,U is exceptional, so that the number of coordinate squares can be bounded by β.
Lemma 2.11. Let J⊆[n] have size 2t+1≥3, where t≤d, and let S∈(tJ). Put PJ,S={U∈RJ,S:e2t+1(FJ,U)=1}. Every coordinate square contained in RJ,S is also contained in PJ,S. Consequently,
c2(RJ,S)=c2(PJ,S)≤(2d−t)∣PJ,S∣.
Moreover,
S∈(tJ)∑∣PJ,S∣≤(t2t+1)U⊆[n]∖J∑e2t+1(FJ,U).
Proof of Lemma 2.11. By the proof of Lemma 2.7, we know if FJ,U is elementary and shatters S, then FJ,U must be (tJ) or (t+1J).
Claim 2.12. If U0⊊U1⊊U2 belong to RJ,S, then all three restricted families FJ,Ui are exceptional.
Proof of claim. Note if U⊊V, then any set in FJ,U can not be contained in any set in FJ,V since F is a Sperner family. We write Ai=FJ,Ui for i=0,1,2.
Now suppose A1=(tJ). Then any set in A2 has size at most t−1. Hence A2 can not shatter S, which is contradictory. In the same way, A0 can not be (tJ). If A1=(t+1J), then any set in A0 has size at least t+2. But the empty trace needs there to exist a set in A0 such that this set is disjoint with S. Note ∣J∣=2t+1 and ∣S∣=t. This is impossible. In the same way, A2 can not be (t+1J).
Now if A0=(t+1J) or A2=(tJ), note A0=(t+1J) means S is contained in A1 since A1 shatters S and any set in A1 has size at most t. Note A2 also shatters S, which means S is contained in some set in A2. This is contradictory. Similarly, A2=(tJ) means J∖S is contained in A1, which is contradictory since A0 shatters S. Therefore, all three families are exceptional. ■
Take any coordinate square Q(B,W) in RJ,S. Then every member of Q(B,W) is contained in a chain U0⊊U1⊊U2. By Claim 2.12 and the definition of PJ,S, we know Q(B,W) is contained in PJ,S. Hence c2(PJ,S)=c2(RJ,S) and by Lemma 2.4, we have VCdim(PJ,S)≤d−t. If d>t, then by Lemma 2.9, we have c2(PJ,S)≤(2d−t)∣PJ,S∣. If d=t and PJ,S contains a coordinate square Q(B,W), then PJ,S can shatter the two-element set W, which contradicts VCdim(PJ,S)≤d−t. So if d=t, we must have c2(RJ,S)=c2(PJ,S)=0. Finally, for a fixed S, ∣PJ,S∣ is the number of restricted families FJ,U such that FJ,U shatters S and e2t+1(FJ,U)=1. Note FJ,U can shatter at most (t2t+1) sets of size t. Then we have the last inequality.
For odd r with 3≤r≤min(2d+1,n−2), put ar(n,d)=br,2r−1⋅(2n−r)((n−r)/2d−(r−1)/2). Now we average the preceding inequality in Lemma 2.8 and show that αr+2≥αr−ar(n,d)βr.
Proposition 2.13. For every odd r with 3≤r≤min(2d+1,n−2), we have
αr+2≥αr−ar(n,d)βr.
Proof of Proposition 2.13. Put t=2r−1. We first choose J∈(r[n]) uniformly, and then choose W∈(2[n]∖J) uniformly. Further, we choose an ordering π of J and an ordering ρ of W uniformly and independently. Let K=J∪W. This is equivalent to choosing K∈(r+2[n]) uniformly and choosing an ordering σ of K uniformly. Now we fix such J,W,π,ρ, and also fix Z⊆[n]∖K. By Lemma 2.8, we have
Now we compute f3. We firstly prove that RS(FK,Z)=2W if and only if Q(Z,W)⊆RJ,S. Recall the definition of RS(A) in Lemma 2.8: RS(A)={T⊆W:S∈Sh(AJ,T)} for S⊆J. Note we have (FK,Z)J,T=FJ,T∪Z, so RS(FK,Z)=2W if and only if S∈Sh((FK,Z)J,T)=Sh(FJ,T∪Z) for every T⊆W, which means T∪Z∈RJ,S. Recall that a coordinate square Q(Z,W) is defined as Q(Z,W)={Z∪T:T⊆W}. Hence RS(FK,Z)=2W if and only if Q(Z,W)⊆RJ,S. So we have
Note that we choose π uniformly, so by Lemma 2.6, we have P(S∈Br(π))=br,t/(tr). Also note that c2(RJ,S) is independent of the choice of ρ, so we have
Even if we know αr≥0, we cannot get αr+2≥0 only by Proposition 2.13. Therefore we need to dig out more information between β and α. Before this, we need several auxiliary results. We first show the whole family F is strongly influenced by the restricted family FJ,U.
Lemma 2.14. Let 3≤p≤m, and let A⊆2[m] be a Sperner family. Suppose that AJ,U is elementary for every J∈(p[m]) and every U⊆[m]∖J. Then either A is elementary, or ∣X△Y∣>p for all distinct X,Y∈A.
Proof of Lemma 2.14. Induction on m. If m=p and there exist two distinct sets X,Y∈A such that ∣X△Y∣≤p, then A must be a complete layer. In fact, in this case, J can only be [m], which means A is elementary. Since A has at least two sets, A must be a complete s layer with 1≤s≤m−1.
Assume that the statement holds for m with m≥p. We prove it for m+1. If there exist two distinct sets X,Y∈A such that ∣X△Y∣≤p, then there exists at least one coordinate not contained in X△Y. So we may suppose i is not contained in either X or Y for some i. Indeed, if we can not take such i, then there exists j, such that j∈X∩Y. So we can take complements for every set in A. Note taking complements preserves the hypothesis, since the complement in J of an elementary restricted family is again elementary.
Without loss of generality, we may further assume that the coordinate i we take is m+1. So X,Y∈2[m] and ∣X△Y∣≤p. By the induction hypothesis, we know that the subfamily of A consisting of all sets not containing m+1 is a complete s layer on the ground set [m] with 1≤s≤m−1. For any B∈(s[m]), B∪{m+1} is also contained in A. In fact, since 1≤s≤m−1, we can take two distinct coordinates a,b outside B∪{m+1}. Note p≥3, so we can choose a set J of size p such that J contains {a,b,m+1}. We take the outside part to be B∖J. Then this restricted family contains at least two members and hence it must be a complete layer, which means B∪{m+1} must be contained in A. So A contains a complete s layer on the ground set [m+1]. Note A is a Sperner family, so no other set can be contained in A. Hence A is a complete s layer on the ground set [m+1] with 1≤s≤m−1.
□
We next compare δˉq(A) with the number of exceptional restricted families AJ,U for ∣J∣=p.
Lemma 2.15. Let p,q be odd with 3≤p<q≤2p−1. Every Sperner family A⊆2[q] satisfies
Proof of Lemma 2.15. If there exists a restricted family AJ,U with ∣J∣=p that is exceptional, then the sum in the statement is at least one. Note A is nonempty and hence shatters the empty set. So by (2), we have δˉq(A)≥1−∣A∣. Using Lemma 2.1, we have ∣A∣≤((q−1)/2q), so the right side of the stated inequality is at least 1−∣A∣+((q−1)/2q)≥1≥eq(A).
Now we suppose every restricted family AJ,U with ∣J∣=p is elementary. If A is elementary, then eq(A)=δˉq(A)=0 by Lemma 2.7. If A is exceptional, then ∣A∣≥2 and Lemma 2.14 gives ∣A△B∣≥p+1 for all distinct A,B∈A.
Claim 2.16.∣A∣≤32(p+1).
Proof of claim. Choose A,B independently and uniformly from A, allowing A=B. For a fixed coordinate, let θ be the proportion of members of A containing it. By independence, A and B differ at this coordinate with probability 2θ(1−θ)≤21. Summing over the q coordinates gives E∣A△B∣≤2q. On the other hand, P(A=B)=∣A∣1, and ∣A△B∣≥p+1 whenever A=B. Thus (p+1)(1−∣A∣1)≤E∣A△B∣≤2q. Since 2(p+1)−q≥3, we have ∣A∣≤2(p+1)−q2(p+1)≤32(p+1).
Fix distinct A,B∈A. For each i∈A△B, one of A and B contains i and the other does not, so {i} is shattered by A. Thus A shatters at least p+1 singletons and the empty set. Note bq,0=1 and bq,1=q−1, so we have δˉq(A)≥1+32(p+1)−∣A∣≥1=eq(A).
For these values of p,q, put cq,p=((q−1)/2q)(pq). Summing Lemma 2.15 over the restricted families gives the following inequality.
Proposition 2.17. For odd p,q with 3≤p<q≤min(2p−1,n), we have
βq≤αq+cq,pβp.
Proof of Proposition 2.17. Fix K∈(q[n]) and Z⊆[n]∖K. For J∈(pK) and T⊆K∖J, we have (FK,Z)J,T={A⊆J:A∪T∪Z∈F}=FJ,Z∪T. For fixed J⊆K, every U⊆[n]∖J has a unique decomposition U=Z∪T, with Z=U∖K and T=U∩(K∖J). Hence we have
We now suppose that n is sufficiently large in terms of d. Combining (6) and (7), we will prove that αq≥0 and βq≤(q−3)6⋅24q−16αq for every odd 5≤q≤2d−1.
Proposition 2.18. For every integer d≥3, put n0(d)=d10⋅25d−10. Then for every n≥n0(d) and every odd q with 5≤q≤2d−1, we have αq≥0 and βq≤(q−3)6⋅24q−16αq.
Proof of Proposition 2.18. For any fixed odd q with 5≤q≤2d−1, put p=2⌈4q+1⌉+1. Then p is the smallest odd integer at least 2q+1. For fixed d and any odd r with p≤r<q, ar(n,d) tends to zero as n tends to infinity. For this fixed d, if n≥d10⋅25d−10, then for any such p,q,r, we have
(1+22q−6⋅p6⋅24p−16)p≤r<qrodd∑ar(n,d)≤21.(8)
In fact, recall that ar(n,d)=(2n)br,2r−1(2n−rd−2r−1) and br,2r−1=(2r−1r)−(2r−3r). Since 5≤q≤2d−1 and p=2⌈4q+1⌉+1, we have 3≤p≤2q+3 and 2q+3≤d+1. Hence we have r≤q−2≤2d−3 and 1≤2r−1≤d−2.
Since 2(2r−1r)≤2r, we have 0≤br,2r−1≤(2r−1r)≤2r−1≤22d−4. We also have (2n−r)≥8n2 since n≥d10⋅25d−10≥4d and r≤2d−3. Note (2d−2r−1)≤2d2, so for any odd r with p≤r<q, we have
ar(n,d)≤n2/822d−4⋅d2/2=n2d2⋅22d−2.(9)
Since q≥5 and p≥3, we have 22q−6⋅p6⋅24p−16=p6⋅22q+4p−22≥1. Note q≤2d−1 and p≤d+1, so we have
Combining (9) and (10), we have (1+22q−6⋅p6⋅24p−16)∑p≤r<qroddar(n,d)≤n2d3(d+1)6⋅210d−21. So we get (8) when n≥d10⋅25d−10. In particular, 0≤ar(n,d)≤1 for every odd r with p≤r<q when n≥d10⋅25d−10.
Now we suppose d≥3 and n≥d10⋅25d−10 are both fixed. Suppose αp≥0 and βp≤(p−3)6⋅24p−16αp if p≥5. Note β3≤3α3 by Lemma 2.7, so in any case, we always have βp≤p6⋅24p−16αp.
Claim 2.19.αq≥21αp.
Proof of claim. Write ar=ar(n,d). Recall that cr,p=((pr)r−1/2r) [sic], so for any odd r with p<r<q, we have cr,p≤22r−2≤22q−6 and hence have βr≤αr+22q−6βp by (7). We also have βp≤αp+22q−6βp since αp,βp≥0 and 22q−6≥1. Substituting this inequality into (6), we have αr+2+22q−6βp≥(1−ar)(αr+22q−6βp). Since 0≤ar≤1 and αp+22q−6βp≥0, we have
αq+22q−6βp≥p≤r<qrodd∏(1−ar)(αp+22q−6βp).
Using ∏p≤r<qrodd(1−ar)≥1−∑p≤r<qroddar, we have αq≥αp−(αp+22q−6βp)∑p≤r<qroddar. By the hypothesis βp≤p6⋅24p−16αp, we have
Since αp≥0 and αq≥21αp, we have αq≥0. On the other hand, using (7), we have βq≤αq+cq,pβp.
If q=5, then p=3 and c5,3=100. Note we have α3≥0 and β3≤3α3 by Lemma 2.7. Using β3≤3α3 and α5≥21α3, we have β5≤α5+100β3≤601α5≤210α5, as required. If q≥7, then p≥5. Since βp≤(p−3)6⋅24p−16αp and αp≤2αq, we have βq≤(1+2cq,p⋅(p−3)6⋅24p−16)αq. Note that q−3≥2(p−3) and p≤2q+3, so (p−3)6⋅24p−16(q−3)6⋅24q−16≥26+4(q−p)≥22q. Also note that cq,p≤22q−2 and cq,p⋅(p−3)6⋅24p−16≥1, so we have
1+2cq,p⋅(p−3)6⋅24p−16≤3cq,p⋅(p−3)6⋅24p−16
≤22q⋅(p−3)6⋅24p−16≤(q−3)6⋅24q−16,
which means βq≤(q−3)6⋅24q−16αq.
For every odd q≥5, p=2⌈4q+1⌉+1 is the smallest odd integer at least 2q+1, and hence 2⌈4p+1⌉+1 is the smallest odd integer at least 2p+1. Repeating this finitely many times, we always get 3. By Lemma 2.7, we have α3≥0 and β3≤3α3. So, by induction, if d is fixed and n≥d10⋅25d−10, then for every odd q with 5≤q≤2d−1, we have αq≥0 and βq≤(q−3)6⋅24q−16αq.
It is enough to prove that α2d−1(F)≥0 to get ∣F∣≤(dn). So we have proved the bound in the main theorem 1.2. The rest of the equality case can be handled by Lemma 2.14.
Proof of Theorem 1.2. By Proposition 2.18, (1) and (3), we have 0≤α2d−1≤(dn)−∣F∣ when n≥d10⋅25d−10. This proves the bound.
Now we suppose that ∣F∣=(dn). Then by Proposition 2.18, we know that α2d−1=0 means that β2d−1=0. Note that β2d−1 is the average number of exceptional restricted families, so β2d−1=0 means that every restricted family is elementary. In other words, for any J∈(2d−1[n]) and any U⊆[n]∖J, FJ,U is elementary.
If F is exceptional, then F has at least two members. By Lemma 2.14, for any two distinct sets X,Y∈F, we have ∣X△Y∣>2d−1. Now we fix J∈(2d−1[n]) and denote H={A∖J:A∈F}⊆2[n]∖J. Note that if A∖J=B∖J for some A,B∈F, then we must have A=B. In fact, if A=B and A∖J=B∖J, then ∣A△B∣>2d−1 and A△B⊆J, but ∣J∣=2d−1, which is impossible. So we have a bijection between F and H. Note that H is a family on the ground set [n]∖J, so any set shattered by H can also be shattered by F. Hence VCdim(H)≤VCdim(F)≤d. Then by Lemma 2.2, we have ∣H∣≤∑j=0d(jn−2d+1). Note that b2d−1,0=1 and b2d−1,1=2d−2>0, so by Lemma 2.5, we have
Hence F must be elementary. Note that ∣F∣=(dn)>1, so it must be a complete s layer with 1≤s≤n−1. Then obviously, s must be d or n−d. This finishes the proof.
Acknowledgement
The authors would like to thank Jian Wang, Yang Shu and Xiaochen Zhao for many helpful discussions.
References
[1]R. Ahlswede and L. H. Khachatrian. Counterexample to the Frankl-Pach conjecture for uniform, dense families. Combinatorica, 17(2):299–301, 1997.DOI
[2]R. P. Anstee and A. Sali. Sperner families of bounded VC-dimension. Discrete Math., 175(1-3):13–21, 1997.DOI
[3]J. Balogh, A. Bernshteyn, M. Delcourt, A. Ferber, and H. T. Pham. Sunflowers in set systems with small VC-dimension. Combinatorica, 45(6):Paper No. 58, 19, 2025.arxiv.org/abs/2408.04165
[4]T.-W. Chao, Z. Xu, C. H. Yip, and S. Zhang. Uniform set systems with small VC-dimension. Int. Math. Res. Not. IMRN, (17):Paper No. rnaf269, 20, 2025.DOI
[5]J. Fox, J. Pach, and A. Suk. Erdős–Hajnal conjecture for graphs with bounded VC-dimension. Discrete Comput. Geom., 61(4):809–829, 2019.arxiv.org/abs/1710.03745
[6]J. Fox, J. Pach, and A. Suk. Bounded VC-dimension implies the Schur–Erdős conjecture. Combinatorica, 41(6):803–813, 2021.arxiv.org/abs/1912.02342
[7]J. Fox, J. Pach, and A. Suk. Sunflowers in set systems of bounded dimension. Combinatorica, 43(1):187–202, 2023.
[8]P. Frankl. Traces of antichains. Graphs Combin., 5(1):295–299, 1989.DOI
[9]P. Frankl and J. Pach. On disjointly representable sets. Combinatorica, 4(1):39–45, 1984.DOI
[10]P. Frankl and J. Wang. Four-vertex traces of finite sets. Graphs Combin., 40(1):Paper No. 8, 2024.arxiv.org/abs/2301.05830
[11]G. Ge, J. Wang, Z. Xu, and X. Zhao. Bounded VC-dimension implies the Erdős–Rado sunflower conjecture, 2026. arXiv:2609.18995.arxiv.org/abs/2609.18995
[12]G. Ge, Z. Xu, C. H. Yip, S. Zhang, and X. Zhao. The Frankl-Pach upper bound is not tight for any uniformity. J. Combin. Theory Ser. A, 217:Paper No. 106078, 9, 2026.DOI
[13]X. Huang, H. Liu, M. Rong, and Z. Xu. Interpolating chromatic and homomorphism thresholds, 2025. arXiv:2502.09576. J. Combin. Theory Ser. B, to appear.arxiv.org/abs/2502.09576
[14]H. Liu, C. Shangguan, J. Skokan, and Z. Xu. Beyond chromatic threshold via the $(p,q)$-theorem, and a sharp blow-up phenomenon, 2024. arXiv:2403.17910.
[15]D. Mubayi and Y. Zhao. On the VC-dimension of uniform hypergraphs. J. Algebraic Combin., 25(1):101–110, 2007.DOI
[16]T. Nguyen, A. Scott, and P. Seymour. Induced subgraph density. VI. Bounded VC-dimension. Adv. Math., 482(part A):Paper No. 110601, 20, 2025.arxiv.org/abs/2312.15572
[17]S. Roman. An introduction to Catalan numbers. Compact Textbooks in Mathematics. Birkhäuser/Springer, Cham, 2015. With a foreword by Richard Stanley.DOI
[18]N. Sauer. On the density of families of sets. J. Combin. Theory Ser. A, 13:145–147, 1972.DOI
[19]S. Shelah. A combinatorial problem; stability and order for models and theories in infinitary languages. Pacific J. Math., 41:247–261, 1972.DOI
[20]E. Sperner. Ein Satz über Untermengen einer endlichen Menge. Math. Z., 27(1):544–548, 1928.DOI
[21]S. Sun, Y. Wang, and J. Zeng. A single exponential Erdős–Hajnal bound for graphs of bounded VC-dimension, 2026. arXiv:2607.09049.arxiv.org/abs/2607.09049
[22]T. Tran and Z. Xu. Beating the Ahlswede–Khachatrian bound for the Erdős–Frankl–Pach problem, 2026. arXiv:2606.23469.arxiv.org/abs/2606.23469
[23]V. N. Vapnik and A. Y. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory Probab. Appl., 16(2):264–280, 1971.
[24]J. Wang, Z. Xu, and S. Zhang. Largest 3-uniform set systems with VC-dimension 2, 2025. arXiv:2505.07756.arxiv.org/abs/2505.07756
[25]T. Yang and X. Yu. Maximum size of a uniform family with bounded VC-dimension, 2025. arXiv:2508.14334.arxiv.org/abs/2508.14334
[26]X. Zhao and G. Ge. Recursive lifting beyond the Ahlswede–Khachatriian construction, 2026. arXiv:2607.04858.arxiv.org/abs/2607.04858