betaFeedback

WorksMathematics

Largest Sperner families with bounded VC-dimension

Abstract

A conjecture of Frankl proposed in the 1980s states that for n≥2dn\ge2d, every Sperner family F⊆2[n]\mathcal{F}\subseteq 2^{[n]} of VC-dimension at most dd has at most (nd)\binom{n}{d} members. We prove this conjecture for every fixed dd and large nn, and show that equality holds only when F\mathcal{F} is ([n]d)\binom{[n]}{d} or ([n]n−d)\binom{[n]}{n-d}.

Introduction

For a finite set VV, write (Vk)={A⊆V:∣A∣=k}\binom{V}{k}=\{A\subseteq V:|A|=k\} and (V≤k)=⋃j=0k(Vj)\binom{V}{\le k}=\bigcup_{j=0}^{k}\binom{V}{j}, and set [n]={1,…,n}[n]=\{1,\ldots,n\}. We call (Vk)\binom{V}{k} the complete layer of sets of size kk. A family F⊆2[n]\mathcal{F}\subseteq2^{[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⌊n/2⌋)|\mathcal{F}|\le\binom{n}{\lfloor n/2\rfloor}, which is sharp.

For S⊆[n]S\subseteq[n], the trace of F\mathcal{F} on SS is F∣S={A∩S:A∈F}\mathcal{F}|_S=\{A\cap S:A\in\mathcal{F}\}. We say that F\mathcal{F} shatters SS if F∣S=2S\mathcal{F}|_S=2^S, and write Sh⁡(F)\operatorname{Sh}(\mathcal{F}) for the family of shattered sets. The Vapnik–Chervonenkis dimension (VC-dimension for short), denoted by VCdim⁡(F)\operatorname{VCdim}(\mathcal{F}), is the largest size of a shattered set. The Sauer–Shelah lemma [18, 19, 23] states that every family with VCdim⁡(F)≤d\operatorname{VCdim}(\mathcal{F})\le d satisfies ∣F∣≤∑i=0d(ni)|\mathcal{F}|\le\sum_{i=0}^{d}\binom{n}{i}. This bound can be attained by ([n]≤d)\binom{[n]}{\le d}. 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+1d+1 with VC-dimension at most dd has size at most (nd)\binom{n}{d} when n≥2dn\ge2d. 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≥2dn\ge2d, the complete layers ([n]d)\binom{[n]}{d} and ([n]n−d)\binom{[n]}{n-d} are Sperner families of VC-dimension dd, each of size (nd)\binom{n}{d}. In 1989, Frankl [8] conjectured that these layers have the largest possible size.

Conjecture 1.1. Let d≥1d\ge1 and n≥2dn\ge2d be integers, and let F⊆2[n]\mathcal{F}\subseteq2^{[n]} be a Sperner family with VCdim⁡(F)≤d\operatorname{VCdim}(\mathcal{F})\le d. Then ∣F∣≤(nd)|\mathcal{F}|\le\binom{n}{d}.

This conjecture brings together Sperner’s theorem and the Sauer–Shelah lemma. When n=2dn=2d or n=2d+1n=2d+1, the proposed bound is exactly the bound in Sperner’s theorem. Frankl [8] proved the cases d=1,2d=1,2, and Anstee and Sali [2] proved the case d=3d=3. Despite subsequent progress on related problems, the cases of Conjecture 1.1 known in the full range n≥2dn\ge2d have remained d≤3d\le3 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≥3d\ge3 and large nn, and determine the extremal families.

Theorem 1.2. For every integer d≥3d\ge3, there exists some n0=n0(d)n_0=n_0(d) such that for every n>n0n>n_0, every Sperner family F⊆2[n]\mathcal{F}\subseteq2^{[n]} with VCdim⁡(F)≤d\operatorname{VCdim}(\mathcal{F})\le d satisfies ∣F∣≤(nd)|\mathcal{F}|\le\binom{n}{d}. Equality holds if and only if F=([n]d)\mathcal{F}=\binom{[n]}{d} or F=([n]n−d)\mathcal{F}=\binom{[n]}{n-d}.

Remark 1.3. Our proof shows that it suffices to take n0(d)=d10⋅25d−10n_0(d)=d^{10}\cdot2^{5d-10}. The main remaining problem is to establish the conjecture in the full range n≥2dn\ge2d.

Frankl [8] provided the general upper bound (nd)+(nd−3)+(nd−6)+⋯\binom{n}{d}+\binom{n}{d-3}+\binom{n}{d-6}+\cdots by a recursive argument and therefore proved the cases d≤2d\le2. Anstee and Sali [2] settled d=3d=3 using induction and a characterization of the extremal families for d=1,2d=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)A\triangle B=(A\setminus B)\cup(B\setminus 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 family A⊆2[n]\mathcal{A}\subseteq2^{[n]} satisfies ∣A∣≤(n⌊n/2⌋)|\mathcal{A}|\le\binom{n}{\lfloor n/2\rfloor}.

Lemma 2.2 ([18, 19, 23]). Let d≥1d\ge1 be an integer and H⊆2[n]\mathcal{H}\subseteq2^{[n]} be a set system with VC-dimension at most dd. Then ∣H∣≤∑j=0d(nj)|\mathcal{H}|\le\sum_{j=0}^{d}\binom{n}{j}.

We also use the result on the ballot problem in enumerative combinatorics [17].

Lemma 2.3 ([17]). Consider an election with two candidates AA and BB where AA receives aa votes and BB receives bb votes, with a≥ba\ge b. Assume that all voting histories are equally likely. The probability that candidate AA is never behind candidate BB is a+1−ba+1\frac{a+1-b}{a+1}.

Transformation of the problem and the proof of Theorem 1.2

Let F⊆2[n]\mathcal{F}\subseteq2^{[n]} be a Sperner family with VCdim⁡(F)≤d\operatorname{VCdim}(\mathcal{F})\le d. For J⊆[n]J\subseteq[n] and U⊆[n]∖JU\subseteq[n]\setminus J, define the restricted family FJ,U={A⊆J:A∪U∈F}\mathcal{F}_{J,U}=\{A\subseteq J:A\cup U\in\mathcal{F}\}. We use this notation for any family on a specified ground set. Every restricted family FJ,U\mathcal{F}_{J,U} is Sperner. For fixed JJ, each F∈FF\in\mathcal{F} has a unique decomposition F=A∪UF=A\cup U with A⊆JA\subseteq J and U⊆[n]∖JU\subseteq[n]\setminus J. Therefore, ∑U⊆[n]∖J∣FJ,U∣=∣F∣\sum_{U\subseteq[n]\setminus J}|\mathcal{F}_{J,U}|=|\mathcal{F}|.

Further, for any S⊆J⊆[n]S\subseteq J\subseteq[n], define the family RJ,S={U⊆[n]∖J:S∈Sh⁡(FJ,U)}\mathcal{R}_{J,S}=\{U\subseteq[n]\setminus J:S\in\operatorname{Sh}(\mathcal{F}_{J,U})\}. We show that any set shattered by RJ,S\mathcal{R}_{J,S} can be joined to SS to give a set shattered by F\mathcal{F}.

Lemma 2.4. If T∈Sh⁡(RJ,S)T\in\operatorname{Sh}(\mathcal{R}_{J,S}), then S∪T∈Sh⁡(F)S\cup T\in\operatorname{Sh}(\mathcal{F}). In particular, VCdim⁡(RJ,S)≤d−∣S∣\operatorname{VCdim}(\mathcal{R}_{J,S})\le d-|S| when ∣S∣≤d|S|\le d, and RJ,S=∅\mathcal{R}_{J,S}=\varnothing when ∣S∣>d|S|>d.

Proof of Lemma 2.4. Note T∈Sh⁡(RJ,S)T\in\operatorname{Sh}(\mathcal{R}_{J,S}) if and only if for any X⊆TX\subseteq T, there exists U∈RJ,SU\in\mathcal{R}_{J,S} such that U∩T=XU\cap T=X. By the definition of RJ,S\mathcal{R}_{J,S}, U∈RJ,SU\in\mathcal{R}_{J,S} if and only if S∈Sh⁡(FJ,U)S\in\operatorname{Sh}(\mathcal{F}_{J,U}). Then for any Y⊆SY\subseteq S, there exists A∈FA\in\mathcal{F}, such that (A∖U)∈FJ,U(A\setminus U)\in\mathcal{F}_{J,U} and (A∖U)∩S=Y(A\setminus U)\cap S=Y. So A∩(S∪T)=X∪YA\cap(S\cup T)=X\cup Y, which means F\mathcal{F} shatters S∪TS\cup T. Note SS is disjoint with TT, so VCdim⁡(RJ,S)≤d−∣S∣\operatorname{VCdim}(\mathcal{R}_{J,S})\le d-|S| when ∣S∣≤d|S|\le d. If RJ,S\mathcal{R}_{J,S} is nonempty and ∣S∣>d|S|>d, then the empty set can be shattered by RJ,S\mathcal{R}_{J,S} and hence SS can be shattered by F\mathcal{F}. This contradicts VCdim⁡(F)≤d\operatorname{VCdim}(\mathcal{F})\le d. □\square

By Lemma 2.4 and Lemma 2.2, we have ∣RJ,S∣≤∑j=0d−∣S∣(n−∣J∣j)|\mathcal{R}_{J,S}|\le\sum_{j=0}^{d-|S|}\binom{n-|J|}{j}. It is not hard to show that for any family A\mathcal{A} on the finite ground set, ∣A∣≤∣Sh⁡(A)∣|\mathcal{A}|\le|\operatorname{Sh}(\mathcal{A})|. Indeed, we can prove it by using the downshift argument in Lemma 2.9. Also note ∣F∣=∑U⊆[n]∖J∣FJ,U∣\lvert\mathcal{F}\rvert=\sum_{U\subseteq[n]\setminus J}\lvert\mathcal{F}_{J,U}\rvert. So we have

∣F∣≤∑U⊆[n]∖J∣Sh⁡(FJ,U)∣=∑S⊆J∣RJ,S∣≤∑s=0min⁡(∣J∣,d)(∣J∣s)∑j=0d−s(n−∣J∣j).\begin{aligned} \lvert\mathcal{F}\rvert&\le\sum_{U\subseteq[n]\setminus J}\lvert\operatorname{Sh}(\mathcal{F}_{J,U})\rvert\\ &=\sum_{S\subseteq J}\lvert\mathcal{R}_{J,S}\rvert\\ &\le\sum_{s=0}^{\min(\lvert J\rvert,d)}\binom{\lvert J\rvert}{s}\sum_{j=0}^{d-s}\binom{n-\lvert J\rvert}{j}. \end{aligned}

However, ∑s=0min⁡(∣J∣,d)(∣J∣s)∑j=0d−s(n−∣J∣j)=∑k=0d∑s=0min⁡(∣J∣,k)(∣J∣s)(n−∣J∣k−s)=∑k=0d(nk)\sum_{s=0}^{\min(\lvert J\rvert,d)}\binom{\lvert J\rvert}{s}\sum_{j=0}^{d-s}\binom{n-\lvert J\rvert}{j}=\sum_{k=0}^{d}\sum_{s=0}^{\min(\lvert J\rvert,k)}\binom{\lvert J\rvert}{s}\binom{n-\lvert J\rvert}{k-s}=\sum_{k=0}^{d}\binom{n}{k}. 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 (nd)\binom{n}{d}, we assign the same nonnegative weight wsw_s to every set of size ss in JJ. In other words, we want to have the identity ∑s=0min⁡(∣J∣,d)(∣J∣s)ws∑j=0d−s(n−∣J∣j)=(nd)\sum_{s=0}^{\min(\lvert J\rvert,d)}\binom{\lvert J\rvert}{s}w_s\sum_{j=0}^{d-s}\binom{n-\lvert J\rvert}{j}=\binom{n}{d}. That is, ∑j=0d(n−∣J∣j)∑s=0min⁡(∣J∣,d−j)(∣J∣s)ws=∑j=0d(n−∣J∣j)(∣J∣d−j)\sum_{j=0}^{d}\binom{n-\lvert J\rvert}{j}\sum_{s=0}^{\min(\lvert J\rvert,d-j)}\binom{\lvert J\rvert}{s}w_s=\sum_{j=0}^{d}\binom{n-\lvert J\rvert}{j}\binom{\lvert J\rvert}{d-j}. So we can choose the weights so that ∑s=0min⁡(∣J∣,k)(∣J∣s)ws=(∣J∣k)\sum_{s=0}^{\min(\lvert J\rvert,k)}\binom{\lvert J\rvert}{s}w_s=\binom{\lvert J\rvert}{k} for every 0≤k≤d0\le k\le d. With such weights, we have ∣J∣≥2d−1\lvert J\rvert\ge2d-1 since wsw_s is nonnegative for every 0≤s≤d0\le s\le d.

Put bp,k=(pk)−(pk−1)b_{p,k}=\binom{p}{k}-\binom{p}{k-1} for integer p>0p>0 and integer 0≤k≤⌊p/2⌋0\le k\le\lfloor p/2\rfloor. If we take ∣J∣=2d−1\lvert J\rvert=2d-1, then we have the following identity.

Lemma 2.5. For every integer n≥2d−1n\ge2d-1, we have

∑s=0d−1b2d−1,s∑j=0d−s(n−2d+1j)=(nd).\sum_{s=0}^{d-1}b_{2d-1,s}\sum_{j=0}^{d-s}\binom{n-2d+1}{j}=\binom{n}{d}.

Proof of Lemma 2.5. Note we have ∑s=0d−1b2d−1,s∑j=0d−s(n−2d+1j)=∑j=0d(n−2d+1j)∑s=0min⁡(d−j,d−1)b2d−1,s\sum_{s=0}^{d-1}b_{2d-1,s}\sum_{j=0}^{d-s}\binom{n-2d+1}{j}=\sum_{j=0}^{d}\binom{n-2d+1}{j}\sum_{s=0}^{\min(d-j,d-1)}b_{2d-1,s} and ∑s=0ab2d−1,s=(2d−1a)\sum_{s=0}^{a}b_{2d-1,s}=\binom{2d-1}{a} for any 0≤a≤d−10\le a\le d-1. Since (2d−1d−1)=(2d−1d)\binom{2d-1}{d-1}=\binom{2d-1}{d}, we have ∑s=0min⁡(d−j,d−1)b2d−1,s=(2d−1d−j)\sum_{s=0}^{\min(d-j,d-1)}b_{2d-1,s}=\binom{2d-1}{d-j} for any 0≤j≤d0\le j\le d. So we have

∑s=0d−1b2d−1,s∑j=0d−s(n−2d+1j)=∑j=0d(n−2d+1j)(2d−1d−j)=(nd).\sum_{s=0}^{d-1}b_{2d-1,s}\sum_{j=0}^{d-s}\binom{n-2d+1}{j} =\sum_{j=0}^{d}\binom{n-2d+1}{j}\binom{2d-1}{d-j} =\binom{n}{d}.

An important observation is that bp,kb_{p,k} is related to the ballot problem. For any J⊆[n]J\subseteq[n] of odd size p≥3p\ge3, let π=(x1,…,xp)\pi=(x_1,\ldots,x_p) be an ordering of JJ. The set {xs1,…,xsk}\{x_{s_1},\ldots,x_{s_k}\} with 1≤s1<⋯<sk≤p1\le s_1<\cdots<s_k\le p is called a ballot set if sj≥2js_j\ge2j for every j∈[k]j\in[k]. We denote Bp(π)B_p(\pi) for the family of ballot sets, including the empty set. Every member of Bp(π)B_p(\pi) has size at most p−12\frac{p-1}{2}.

Lemma 2.6. For 0≤k≤p−120\le k\le\frac{p-1}{2}, there are exactly bp,kb_{p,k} members of Bp(π)B_p(\pi) having size kk. If S∈(Jk)S\in\binom{J}{k} and π\pi is chosen uniformly at random, then P(S∈Bp(π))=bp,k/(pk)\mathbb{P}(S\in B_p(\pi))=b_{p,k}/\binom{p}{k}. If ∣J∣=2d−1\lvert J\rvert=2d-1, then for any ordering π\pi of JJ, we have

∑S∈B2d−1(π)∣RJ,S∣≤(nd).\sum_{S\in B_{2d-1}(\pi)}\lvert\mathcal{R}_{J,S}\rvert\le\binom{n}{d}.

Proof of Lemma 2.6. We can see SS as a subset of [p][p] of size kk if we see JJ as [p][p]. For a fixed subset SS of size kk, we call an element in [p][p] selected if SS contains this element, and unselected otherwise. Then by the definition of Bp(π)B_p(\pi), a nonempty subset of JJ is contained in Bp(π)B_p(\pi) if and only if the unselected element is never behind the selected element. By Lemma 2.3, we have ∣Bp(π)∩(Jk)∣=p−2k+1p−k+1(pk)=bp,k\lvert\mathcal{B}_p(\pi) \cap\binom{J}{k} \rvert= \frac{p-2k+1}{p-k+1}\binom{p}{k}=b_{p,k} and P(S∈Bp(π))=bp,k/(pk)\mathbb{P}(S \in\mathcal{B}_p(\pi))=b_{p,k}/\binom{p}{k} when the orderings are uniformly distributed.

Now suppose ∣J∣=2d−1\lvert J\rvert=2d-1. Then for any ordering π\pi of JJ, by Lemma 2.2, we have

∑S∈B2d−1(π)∣RJ,S∣≤∑S∈B2d−1(π)∑j=0d−∣S∣(n−2d+1j).\sum_{S\in\mathcal{B}_{2d-1}(\pi)}\lvert R_{J,S}\rvert\leq\sum_{S\in\mathcal{B}_{2d-1}(\pi)}\sum_{j=0}^{d-\lvert S\rvert}\binom{n-2d+1}{j}.

Since ∣B2d−1(π)∩(Jk)∣=b2d−1,k\left\lvert\mathcal{B}_{2d-1}(\pi)\cap\binom{J}{k}\right\rvert=b_{2d-1,k}, by Lemma 2.5, we have

∑S∈B2d−1(π)∣RJ,S∣≤∑s=0d−1b2d−1,s∑j=0d−s−1(n−2d+1j)=(nd).\sum_{S\in\mathcal{B}_{2d-1}(\pi)}\lvert R_{J,S}\rvert\leq\sum_{s=0}^{d-1}b_{2d-1,s}\sum_{j=0}^{d-s-1}\binom{n-2d+1}{j}=\binom{n}{d}.

For any J⊆[n]J\subseteq[n] with ∣J∣=2d−1\lvert J\rvert=2d-1 and any ordering π\pi of JJ, by the definition of RJ,SR_{J,S}, Lemma 2.6 and double counting the pairs (U,S)(U,S) with U⊆[n]∖JU\subseteq[n]\setminus J and S∈Sh⁡(FJ,U)∩B2d−1(π)S\in\operatorname{Sh}(\mathcal{F}_{J,U})\cap\mathcal{B}_{2d-1}(\pi), we have

∑S∈B2d−1(π)∣RJ,S∣=∑U⊆[n]∖J∣Sh⁡(FJ,U)∩B2d−1(π)∣≤(nd).\sum_{S\in\mathcal{B}_{2d-1}(\pi)}\lvert R_{J,S}\rvert=\sum_{U\subseteq[n]\setminus J}\left\lvert\operatorname{Sh}(\mathcal{F}_{J,U})\cap\mathcal{B}_{2d-1}(\pi)\right\rvert\leq\binom{n}{d}.

Note we want to prove ∣F∣≤(nd)\lvert\mathcal{F}\rvert\leq\binom{n}{d}. Using ∣F∣=∑U⊆[n]∖J∣FJ,U∣\lvert\mathcal{F}\rvert=\sum_{U\subseteq[n]\setminus J}\lvert\mathcal{F}_{J,U}\rvert, we have

∑U⊆[n]∖J(∣Sh⁡(FJ,U)∩B2d−1(π)∣−∣FJ,U∣)≤(nd)−∣F∣.(1)\sum_{U\subseteq[n]\setminus J}\left(\left\lvert\operatorname{Sh}(\mathcal{F}_{J,U})\cap\mathcal{B}_{2d-1}(\pi)\right\rvert-\lvert\mathcal{F}_{J,U}\rvert\right)\leq\binom{n}{d}-\lvert\mathcal{F}\rvert. \tag*{(1)}

For any A⊆2J\mathcal{A}\subseteq2^J with J⊆[n]J\subseteq[n] having odd size p≥3p\geq3 and any ordering π\pi of JJ, we define δp,π(A)=∣Sh⁡(A)∩Bp(π)∣−∣A∣\delta_{p,\pi}(\mathcal{A})=\lvert\operatorname{Sh}(\mathcal{A})\cap\mathcal{B}_p(\pi)\rvert-\lvert\mathcal{A}\rvert and δˉp(A)=Eπδp,π(A)\bar{\delta}_p(\mathcal{A})=\mathbb{E}_{\pi}\delta_{p,\pi}(\mathcal{A}), where all p!p! orderings of JJ are chosen uniformly. Lemma 2.6 gives

δˉp(A)=∑k=0(p−1)/2bp,k(pk)∣Sh⁡(A)∩(Jk)∣−∣A∣.(2)\bar{\delta}_p(\mathcal{A})=\sum_{k=0}^{(p-1)/2}\frac{b_{p,k}}{\binom{p}{k}}\left\lvert\operatorname{Sh}(\mathcal{A})\cap\binom{J}{k}\right\rvert-\lvert\mathcal{A}\rvert. \tag*{(2)}

We can also average over all J∈([n]p)J\in\binom{[n]}{p}. Therefore for odd 3≤p≤n3\leq p\leq n, we define

αp(F)=1(np)∑J∈([n]p)∑U⊆[n]∖Jδˉp(FJ,U).(3)\alpha_p(\mathcal{F})=\frac{1}{\binom{n}{p}}\sum_{J\in\binom{[n]}{p}}\sum_{U\subseteq[n]\setminus J}\bar{\delta}_p(\mathcal{F}_{J,U}). \tag*{(3)}

Averaging (1) over all J∈([n]2d−1)J\in\binom{[n]}{2d-1} and all orderings π\pi of JJ, and using (2) and (3), we know that to prove ∣F∣≤(nd)\lvert\mathcal{F}\rvert\leq\binom{n}{d}, it is enough to show that α2d−1(F)≥0\alpha_{2d-1}(\mathcal{F})\geq0. Indeed, we could also determine all families attaining equality via our approach.

A family on a specified finite set JJ is called elementary if it is empty, consists of one set, or equals (Js)\binom{J}{s} for some 0≤s≤∣J∣0\leq s\leq\lvert J\rvert. We call all other families exceptional. For A⊆2J\mathcal{A}\subseteq2^J with ∣J∣=p\lvert J\rvert=p, put ep(A)=0e_p(\mathcal{A})=0 if A\mathcal{A} is elementary and ep(A)=1e_p(\mathcal{A})=1 otherwise. In particular, A⊊(Js)\mathcal{A}\subsetneq\binom{J}{s} is exceptional whenever ∣A∣≥2\lvert\mathcal{A}\rvert\geq2. Corresponding to (3), for odd 3≤p≤n3\leq p\leq n, we also define

βp(F)=1(np)∑J∈([n]p)∑U⊆[n]∖Jep(FJ,U).(4)\beta_p(\mathcal{F})=\frac{1}{\binom{n}{p}}\sum_{J\in\binom{[n]}{p}}\sum_{U\subseteq[n]\setminus J}e_p(\mathcal{F}_{J,U}). \tag*{(4)}

Note the complete layer ([n]d)\binom{[n]}{d} attains the desired bound (nd)\binom{n}{d}, and every nonempty restricted family of the complete layer ([n]d)\binom{[n]}{d} must be a complete layer. Therefore we will show β2d−1(F)=0\beta_{2d-1}(\mathcal{F})=0 when α2d−1(F)=0\alpha_{2d-1}(\mathcal{F})=0.

For the fixed family F\mathcal{F}, write αp=αp(F)\alpha_p=\alpha_p(\mathcal{F}) and βp=βp(F)\beta_p=\beta_p(\mathcal{F}). However, it is hard to prove α2d−1≥0\alpha_{2d-1}\geq0 directly. Therefore, we will firstly prove α3≥0\alpha_3\geq0 and β3≤3α3\beta_3\leq3\alpha_3 in Lemma 2.7. Starting from $\alpha_3\geq0 and β3≤3α3\beta_3 \le3\alpha_3, we repeatedly lift JJ by two coordinates to prove αq≥0\alpha_q \ge0 and βq≤Mqαq\beta_q \le M_q\alpha_q for every odd 5≤q≤2d−15 \le q \le2d-1 when nn is sufficiently large in terms of dd. Here MqM_q is a positive number only depending on qq when nn and dd are both fixed. We will show that MqM_q can be chosen as (q−3)62q−16(q-3)6^{2q-16} in Proposition 2.18.

We firstly prove that for every ordering π\boldsymbol{\pi}, δp,π\delta_{p,\pi} vanishes on every elementary family. On three coordinates, δ‾3\overline{\delta}_3 is strictly positive for every exceptional Sperner family.

Lemma 2.7. Every elementary family A\mathcal{A} on a ground set JJ of odd size p≥3p \ge3 satisfies δp,π(A)=0\delta_{p,\pi}(\mathcal{A}) = 0 for every ordering π\pi of JJ, and hence δ‾p(A)=0\overline{\delta}_p(\mathcal{A}) = 0. Every Sperner family A\mathcal{A} on a three-element ground set satisfies δ‾3(A)≥0\overline{\delta}_3(\mathcal{A}) \ge0 and e3(A)≤3δ‾3(A)e_3(\mathcal{A}) \le3\overline{\delta}_3(\mathcal{A}).

Proof of Lemma 2.7. Recall that δp,π(A)=∣Sh⁡(A)∩Bp(π)∣−∣A∣\delta_{p,\pi}(\mathcal{A}) = \lvert\operatorname{Sh}(\mathcal{A}) \cap\mathcal{B}_p(\pi)\rvert- \lvert\mathcal{A}\rvert and δ‾p(A)=Eπδp,π(A)\overline{\delta}_p(\mathcal{A}) = \mathbb{E}_{\pi}\delta_{p,\pi}(\mathcal{A}). If A\mathcal{A} is the empty family, then δp,π(A)=0\delta_{p,\pi}(\mathcal{A}) = 0 for any ordering π\pi since the empty family can not shatter any set. If A\mathcal{A} is a family consisting of only one set, then A\mathcal{A} can only shatter the empty set. Hence δ‾p(A)=0\overline{\delta}_p(\mathcal{A}) = 0 for these two cases.

Now we suppose A\mathcal{A} is a complete ss layer with 1≤s≤p1 \le s \le p. Then A⊆JA \subseteq J is shattered by A\mathcal{A} if and only if ∣A∣≤min⁡(s,p−s)\lvert A\rvert\le\min(s,p-s). In fact, the empty trace needs A\mathcal{A} to have a set disjoint with AA, and the full trace needs A\mathcal{A} to have a set containing AA. So ∣A∣≤s\lvert A\rvert\le s and ∣A∣≤p−s\lvert A\rvert\le p-s. Conversely, suppose ∣A∣≤min⁡(s,p−s)\lvert A\rvert\le\min(s,p-s). For any subset of AA, we can add some elements in J∖AJ\setminus A to this subset to get a set of size ss. Hence by Lemma 2.6, we have ∣Sh⁡(A)∩Bp(π)∣=∑k=0min⁡(s,p−s)bp,k=(ps)=∣A∣\lvert\operatorname{Sh}(\mathcal{A}) \cap\mathcal{B}_p(\pi)\rvert= \sum_{k=0}^{\min(s,p-s)} b_{p,k} = \binom{p}{s} = \lvert\mathcal{A}\rvert for every ordering π\pi. So δ‾p(A)=0\overline{\delta}_p(\mathcal{A}) = 0 if A\mathcal{A} is a complete layer.

Now we suppose A\mathcal{A} is a Sperner family on a ground set JJ with ∣J∣=3\lvert J\rvert= 3. If A\mathcal{A} is exceptional, then ∣A∣\lvert\mathcal{A}\rvert must be 2 since A\mathcal{A} is a Sperner family. If A\mathcal{A} is contained in a complete 1 layer, then A\mathcal{A} can only shatter the empty set and the sets contained in A\mathcal{A}. Note b3,0=1b_{3,0}=1 and b3,1=2b_{3,1}=2. Then by (2), we have δ‾3(A)=13\overline{\delta}_3(\mathcal{A}) = \frac{1}{3}. In the same way, if A\mathcal{A} is contained in a complete 2 layer, then δ‾3(A)=13\overline{\delta}_3(\mathcal{A}) = \frac{1}{3}. If A\mathcal{A} consists of one singleton and one two-element set, then these two sets must be disjoint since A\mathcal{A} is Sperner. Then A\mathcal{A} can shatter the empty set and all singletons. So δ‾3(A)=1\overline{\delta}_3(\mathcal{A}) = 1. If A\mathcal{A} is elementary, then e3(A)=0e_3(\mathcal{A}) = 0 and δ‾3(A)=0\overline{\delta}_3(\mathcal{A}) = 0. Hence δ‾3(A)≥0\overline{\delta}_3(\mathcal{A}) \ge0 and e3(A)≤3δ‾3(A)e_3(\mathcal{A}) \le3\overline{\delta}_3(\mathcal{A}) for any Sperner family A\mathcal{A} on a three-element ground set. □\square

We now lift JJ by two coordinates. Ideally, we would like to get αr≤αr+2\alpha_r \le\alpha_{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,WJ,W and orderings π\pi of JJ and ρ\rho of WW, let πρ\pi\rho denote the ordering of J∪WJ\cup W obtained by listing the elements of JJ in the order π\pi, followed by the elements of WW in the order ρ\rho.

Lemma 2.8. Let r=2t+1≥3r=2t+1 \ge3 and K=J∪WK=J\cup W, where J∩W=∅J\cap W=\varnothing, ∣J∣=r\lvert J\rvert=r and ∣W∣=2\lvert W\rvert=2. Fix orderings π\pi of JJ and ρ\rho of WW. For A⊆2K\mathcal{A}\subseteq2^K, put RS(A)={T⊆W:S∈Sh⁡(AJ,T)}\mathcal{R}_S(\mathcal{A})=\{T\subseteq W:S\in\operatorname{Sh}(\mathcal{A}_{J,T})\} for S⊆JS\subseteq J. Then

δr+2,πρ(A)≥∑T⊆Wδr,π(AJ,T)−∣{S∈Br(π):∣S∣=t,RS(A)=2W}∣.(5)\delta_{r+2,\pi\rho}(\mathcal{A}) \ge\sum_{T\subseteq W}\delta_{r,\pi}(\mathcal{A}_{J,T})-\left\lvert\{S\in\mathcal{B}_r(\pi):\lvert S\rvert=t,\mathcal{R}_S(\mathcal{A})=2^W\}\right\rvert. \tag*{(5)}

Proof of Lemma 2.8. As in the proof of Lemma 2.4, if we fix S⊆JS\subseteq J, then for any T∈Sh⁡(RS(A))T\in\operatorname{Sh}(\mathcal{R}_S(\mathcal{A})), we have S∪T∈Sh⁡(A)S\cup T\in\operatorname{Sh}(\mathcal{A}). Now we fix S∈Br(π)S\in\mathcal{B}_r(\pi) with ∣S∣=k\lvert S\rvert=k, where 0≤k≤t0\le k\le t. If k<tk<t, then for any T⊆WT\subseteq W, we have S∪T∈Br+2(πρ)S\cup T\in\mathcal{B}_{r+2}(\pi\rho), since r+1≥2(k+1)r+1\ge2(k+1) and r+2≥2(k+2)r+2\ge2(k+2). In the same way, if k=tk=t and T⊊WT\subsetneq W, we also have S∪T∈Br+2(πρ)S\cup T\in\mathcal{B}_{r+2}(\pi\rho). So we have

∣Sh⁡(A)∩Br+2(πρ)∣≥∑S∈Br(π)∣S∣<t∣Sh⁡(RS(A))∣+∑S∈Br(π)∣S∣=t∣Sh⁡(RS(A))∩{T⊆W:∣T∣≤1}∣.\lvert\operatorname{Sh}(\mathcal{A})\cap\mathcal{B}_{r+2}(\pi\rho)\rvert\ge\sum_{\substack{S\in\mathcal{B}_r(\pi)\\\lvert S\rvert<t}}\lvert\operatorname{Sh}(\mathcal{R}_S(\mathcal{A}))\rvert+\sum_{\substack{S\in\mathcal{B}_r(\pi)\\\lvert S\rvert=t}}\lvert\operatorname{Sh}(\mathcal{R}_S(\mathcal{A}))\cap\{T\subseteq W:\lvert T\rvert\le1\}\rvert.

Note that for any R⊆2W\mathcal{R} \subseteq2^{W}, we have ∣Sh⁡(R)∣≥∣R∣|\operatorname{Sh}(\mathcal{R})| \ge|\mathcal{R}| and ∣Sh⁡(R)∩{T⊆W:∣T∣≤1}∣|\operatorname{Sh}(\mathcal{R}) \cap\{T \subseteq W : |T| \le1\}| is at least ∣R∣−1{R=2W}|\mathcal{R}| - 1_{\{\mathcal{R}=2^{W}\}}. Here 11 is the characteristic function: 1{R=2W}=11_{\{\mathcal{R}=2^{W}\}}=1 if and only if R=2W\mathcal{R}=2^{W}, and 1{R=2W}=01_{\{\mathcal{R}=2^{W}\}}=0 otherwise. So we have

∣Sh⁡(A)∩Br+2(πρ)∣≥∑S∈Br(π)∣RS(A)∣−∑S∈Br(π)∣S∣=t1{RS(A)=2W}.|\operatorname{Sh}(\mathcal{A}) \cap\mathcal{B}_{r+2}(\pi\rho)| \ge\sum_{S\in\mathcal{B}_{r}(\pi)} |\mathcal{R}_{S}(\mathcal{A})|-\sum_{\substack{S\in\mathcal{B}_{r}(\pi)\\ |S|=t}}1_{\{\mathcal{R}_{S}(\mathcal{A})=2^{W}\}}.

By the definition of RS(A)\mathcal{R}_{S}(\mathcal{A}), we know ∣RS(A)∣=∑T⊆W1{S∈Sh⁡(AJ,T)}|\mathcal{R}_{S}(\mathcal{A})|=\sum_{T\subseteq W}1_{\{S\in\operatorname{Sh}(\mathcal{A}_{J,T})\}}, therefore

∑S∈Br(π)∣RS(A)∣=∑S∈Br(π)∑T⊆W1{S∈Sh⁡(AJ,T)}=∑T⊆W∑S∈Br(π)1{S∈Sh⁡(AJ,T)∩Br(π)}=∑T⊆W∣Sh⁡(AJ,T)∩Br(π)∣.\begin{aligned} \sum_{S\in\mathcal{B}_{r}(\pi)}|\mathcal{R}_{S}(\mathcal{A})| &=\sum_{S\in\mathcal{B}_{r}(\pi)}\sum_{T\subseteq W}1_{\{S\in\operatorname{Sh}(\mathcal{A}_{J,T})\}}\\ &=\sum_{T\subseteq W}\sum_{S\in\mathcal{B}_{r}(\pi)}1_{\{S\in\operatorname{Sh}(\mathcal{A}_{J,T})\cap\mathcal{B}_{r}(\pi)\}}\\ &=\sum_{T\subseteq W}|\operatorname{Sh}(\mathcal{A}_{J,T})\cap\mathcal{B}_{r}(\pi)|. \end{aligned}

Note that ∣A∣=∑T⊆W∣AJ,T∣|\mathcal{A}|=\sum_{T\subseteq W}|\mathcal{A}_{J,T}| and recall δr+2,πρ(A)=∣Sh⁡(A)∩Br+2(πρ)∣−∣A∣\delta_{r+2,\pi\rho}(\mathcal{A})=|\operatorname{Sh}(\mathcal{A})\cap\mathcal{B}_{r+2}(\pi\rho)|-|\mathcal{A}|, so we have

δr+2,πρ(A)≥∑T⊆Wδr,π(AJ,T)−∣{S∈Br(π):∣S∣=t,RS(A)=2W}∣.\delta_{r+2,\pi\rho}(\mathcal{A})\ge\sum_{T\subseteq W}\delta_{r,\pi}(\mathcal{A}_{J,T})-\left|\{S\in\mathcal{B}_{r}(\pi):|S|=t,\mathcal{R}_{S}(\mathcal{A})=2^{W}\}\right|.

Now we will average the inequality in Lemma 2.8 to show the inequality between αr\alpha_r and αr+2\alpha_{r+2}. Before this, we need some lemma to handle the error term ∣{S∈Br(π):∣S∣=t,RS(A)=2W}∣\left|\{S\in\mathcal{B}_{r}(\pi):|S|=t,\mathcal{R}_{S}(\mathcal{A})=2^{W}\}\right|.

Let H⊆2[m]\mathcal{H}\subseteq2^{[m]} and i∈[m]i\in[m]. For each H∈HH\in\mathcal{H}, define

H↓i={H∖{i},if i∈H and H∖{i}∉H,H,otherwise.H^{\downarrow i}= \begin{cases} H\setminus\{i\}, & \text{if }i\in H\text{ and }H\setminus\{i\}\notin\mathcal{H},\\ H, & \text{otherwise}. \end{cases}

The downshift of H\mathcal{H} at coordinate ii is the family H↓i={H↓i:H∈H}\mathcal{H}^{\downarrow i}=\{H^{\downarrow i}:H\in\mathcal{H}\}. A coordinate square is Q(B,W)={B∪T:T⊆W}Q(B,W)=\{B\cup T:T\subseteq W\}, where ∣W∣=2|W|=2 and B∩W=∅B\cap W=\varnothing. We write c2(H)c_2(\mathcal{H}) for the number of pairs (B,W)(B,W) such that Q(B,W)⊆HQ(B,W)\subseteq\mathcal{H}.

The following lemma bounds the number of coordinate squares.

Lemma 2.9. Let a≥1a\ge1 be an integer and H⊆2[m]\mathcal{H}\subseteq2^{[m]} be a set system with VCVC-dimension at most $a. Then c2(H)≤(a2)∣H∣c_2(\mathcal{H})\le\binom{a}{2}|\mathcal{H}|.

Proof of Lemma 2.9. By the definition of downshift, we know ∣H∣=∣H↓i∣|\mathcal{H}|=|\mathcal{H}^{\downarrow i}|. Now suppose S∈Sh⁡(H↓i)S\in\operatorname{Sh}(\mathcal{H}^{\downarrow i}). If i∈Si\in S, then for any T⊆S∖{i}T\subseteq S\setminus\{i\}, we have H∈H↓iH\in\mathcal{H}^{\downarrow i} such that H∩S=T∪{i}H\cap S=T\cup\{i\}. By the definition of downshift, we know HH and H∖{i}H\setminus\{i\} are both contained in H\mathcal{H}, which means H\mathcal{H} shatters SS. If i∉Si\notin S, then for any T⊆ST\subseteq S, we have H∈H↓iH\in\mathcal{H}^{\downarrow i} such that H∩S=TH\cap S=T. H\mathcal{H} shatters SS since at least one of H∖{i}H\setminus\{i\} and H∪{i}H\cup\{i\} is contained in H\mathcal{H}. So Sh⁡(H↓i)⊆Sh⁡(H)\operatorname{Sh}(\mathcal{H}^{\downarrow i})\subseteq\operatorname{Sh}(\mathcal{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)Q(B,W) with W={i,j}W=\{i,j\} is contained in H\mathcal{H}, then Q(B,W)Q(B,W) is contained in H↓i\mathcal{H}^{\downarrow i} after the downshifting of H\mathcal{H} at ii. Now we suppose i∉B∪Wi\notin B\cup W. If both Q(B,W)Q(B,W) and Q(B∪{i},W)Q(B\cup\{i\},W) are contained in H\mathcal{H}, then any member in Q(B∪{i},W)Q(B\cup\{i\},W) cannot delete ii since Q(B,W)Q(B,W) is contained in H\mathcal{H}. If only one of the Q(B,W)Q(B,W) and Q(B∪{i},W)Q(B\cup\{i\},W) is contained in H\mathcal{H}, then we have Q(B,W)⊆H↓iQ(B,W)\subseteq\mathcal{H}^{\downarrow i}. In fact, if Q(B∪{i},W)⊆HQ(B\cup\{i\},W)\subseteq\mathcal{H} and Q(B,W)⊈HQ(B,W)\not\subseteq\mathcal{H}, then any member in Q(B,W)Q(B,W) but not in H\mathcal{H} can be obtained after the downshifting of H\mathcal{H} at ii. The other case is obvious. Note every coordinate square with i∉Wi\notin W belongs to exactly one such pair, so the number of coordinate squares cannot decrease after downshifting. ▪

Note if AA contains ii and belongs to H↓i\mathcal{H}^{\downarrow i}, then we can not delete ii in AA since A∖{i}A\setminus\{i\} is already in H↓i\mathcal{H}^{\downarrow i}. So after the downshifting of H\mathcal{H} at ii, we can not delete ii in any set containing ii. Moreover, a downshift at another coordinate preserves this property. Let C\mathcal{C} be the family obtained by downshifting H\mathcal{H} at each coordinate once for any ordering. So we can not delete any coordinate in C\mathcal{C}. We also have ∣C∣=∣H∣|\mathcal{C}|=|\mathcal{H}| and Sh⁡(C)⊆Sh⁡(H)\operatorname{Sh}(\mathcal{C})\subseteq\operatorname{Sh}(\mathcal{H}). Any set in C\mathcal{C} can be shattered by C\mathcal{C} since every subset of this set is already contained in C\mathcal{C}. So any set in C\mathcal{C} has size at most aa. Note a coordinate square Q(B,W)Q(B,W) is contained in C\mathcal{C} if and only if B∪WB\cup W is contained in C\mathcal{C}. Hence by Claim 2.10, we have

c2(H)≤c2(C)=∑A∈C(∣A∣2)≤(a2)∣C∣=(a2)∣H∣.c_2(\mathcal{H})\leq c_2(\mathcal{C})=\sum_{A\in\mathcal{C}}\binom{|A|}{2}\leq\binom{a}{2}|\mathcal{C}|=\binom{a}{2}|\mathcal{H}|.

Suppose that ∣J∣=2t+1|J|=2t+1 and ∣S∣=t|S|=t. We will show that if UU belongs to a coordinate square in RJ,S\mathcal{R}_{J,S}, then FJ,U\mathcal{F}_{J,U} is exceptional, so that the number of coordinate squares can be bounded by β\beta.

Lemma 2.11. Let J⊆[n]J\subseteq[n] have size 2t+1≥32t+1\geq3, where t≤dt\leq d, and let S∈(Jt)S\in\binom{J}{t}. Put PJ,S={U∈RJ,S:e2t+1(FJ,U)=1}\mathcal{P}_{J,S}=\{U\in\mathcal{R}_{J,S}:e_{2t+1}(\mathcal{F}_{J,U})=1\}. Every coordinate square contained in RJ,S\mathcal{R}_{J,S} is also contained in PJ,S\mathcal{P}_{J,S}. Consequently,

c2(RJ,S)=c2(PJ,S)≤(d−t2)∣PJ,S∣.c_2(\mathcal{R}_{J,S})=c_2(\mathcal{P}_{J,S})\leq\binom{d-t}{2}|\mathcal{P}_{J,S}|.

Moreover,

∑S∈(Jt)∣PJ,S∣≤(2t+1t)∑U⊆[n]∖Je2t+1(FJ,U).\sum_{S\in\binom{J}{t}}|\mathcal{P}_{J,S}|\leq\binom{2t+1}{t}\sum_{U\subseteq[n]\setminus J}e_{2t+1}(\mathcal{F}_{J,U}).

Proof of Lemma 2.11. By the proof of Lemma 2.7, we know if FJ,U\mathcal{F}_{J,U} is elementary and shatters SS, then FJ,U\mathcal{F}_{J,U} must be (Jt)\binom{J}{t} or (Jt+1)\binom{J}{t+1}.

Claim 2.12. If U0⊊U1⊊U2U_0\subsetneq U_1\subsetneq U_2 belong to RJ,S\mathcal{R}_{J,S}, then all three restricted families FJ,Ui\mathcal{F}_{J,U_i} are exceptional.

Proof of claim. Note if U⊊VU\subsetneq V, then any set in FJ,U\mathcal{F}_{J,U} can not be contained in any set in FJ,V\mathcal{F}_{J,V} since F\mathcal{F} is a Sperner family. We write Ai=FJ,UiA_i=\mathcal{F}_{J,U_i} for i=0,1,2i=0,1,2.

Now suppose A1=(Jt)A_1=\binom{J}{t}. Then any set in A2A_2 has size at most t−1t-1. Hence A2A_2 can not shatter SS, which is contradictory. In the same way, A0A_0 can not be (Jt)\binom{J}{t}. If A1=(Jt+1)A_1=\binom{J}{t+1}, then any set in A0A_0 has size at least t+2t+2. But the empty trace needs there to exist a set in A0A_0 such that this set is disjoint with SS. Note ∣J∣=2t+1|J|=2t+1 and ∣S∣=t|S|=t. This is impossible. In the same way, A2A_2 can not be (Jt+1)\binom{J}{t+1}.

Now if A0=(Jt+1)A_0=\binom{J}{t+1} or A2=(Jt)A_2=\binom{J}{t}, note A0=(Jt+1)A_0=\binom{J}{t+1} means SS is contained in A1A_1 since A1A_1 shatters SS and any set in A1A_1 has size at most tt. Note A2A_2 also shatters SS, which means SS is contained in some set in A2A_2. This is contradictory. Similarly, A2=(Jt)A_2=\binom{J}{t} means J∖SJ\setminus S is contained in A1A_1, which is contradictory since A0A_0 shatters SS. Therefore, all three families are exceptional. ■

Take any coordinate square Q(B,W)Q(B,W) in RJ,S\mathcal{R}_{J,S}. Then every member of Q(B,W)Q(B,W) is contained in a chain U0⊊U1⊊U2U_0\subsetneq U_1\subsetneq U_2. By Claim 2.12 and the definition of PJ,S\mathcal{P}_{J,S}, we know Q(B,W)Q(B,W) is contained in PJ,S\mathcal{P}_{J,S}. Hence c2(PJ,S)=c2(RJ,S)c_2(\mathcal{P}_{J,S})=c_2(\mathcal{R}_{J,S}) and by Lemma 2.4, we have VCdim⁡(PJ,S)≤d−t\operatorname{VCdim}(\mathcal{P}_{J,S})\leq d-t. If d>td>t, then by Lemma 2.9, we have c2(PJ,S)≤(d−t2)∣PJ,S∣c_2(\mathcal{P}_{J,S})\leq\binom{d-t}{2}|\mathcal{P}_{J,S}|. If d=td=t and PJ,S\mathcal{P}_{J,S} contains a coordinate square Q(B,W)Q(B,W), then PJ,S\mathcal{P}_{J,S} can shatter the two-element set WW, which contradicts VCdim⁡(PJ,S)≤d−t\operatorname{VCdim}(\mathcal{P}_{J,S})\leq d-t. So if d=td=t, we must have c2(RJ,S)=c2(PJ,S)=0c_2(\mathcal{R}_{J,S})=c_2(\mathcal{P}_{J,S})=0. Finally, for a fixed SS, ∣PJ,S∣|\mathcal{P}_{J,S}| is the number of restricted families FJ,U\mathcal{F}_{J,U} such that FJ,U\mathcal{F}_{J,U} shatters SS and e2t+1(FJ,U)=1e_{2t+1}(\mathcal{F}_{J,U})=1. Note FJ,U\mathcal{F}_{J,U} can shatter at most (2t+1t)\binom{2t+1}{t} sets of size tt. Then we have the last inequality.

For odd rr with 3≤r≤min⁡(2d+1,n−2)3\leq r\leq\min(2d+1,n-2), put ar(n,d)=br,r−12⋅(d−(r−1)/2(n−r)/2)(n−r2)a_r(n,d)=b_{r,\frac{r-1}{2}}\cdot\frac{\binom{d-(r-1)/2}{(n-r)/2}}{\binom{n-r}{2}}. Now we average the preceding inequality in Lemma 2.8 and show that αr+2≥αr−ar(n,d)βr\alpha_{r+2}\geq\alpha_r-a_r(n,d)\beta_r.

Proposition 2.13. For every odd rr with 3≤r≤min⁡(2d+1,n−2)3\leq r\leq\min(2d+1,n-2), we have

αr+2≥αr−ar(n,d)βr.\alpha_{r+2}\geq\alpha_r-a_r(n,d)\beta_r.

Proof of Proposition 2.13. Put t=r−12t=\frac{r-1}{2}. We first choose J∈([n]r)J\in\binom{[n]}{r} uniformly, and then choose W∈([n]∖J2)W\in\binom{[n]\setminus J}{2} uniformly. Further, we choose an ordering π\pi of JJ and an ordering ρ\rho of WW uniformly and independently. Let K=J∪WK=J\cup W. This is equivalent to choosing K∈([n]r+2)K\in\binom{[n]}{r+2} uniformly and choosing an ordering σ\sigma of KK uniformly. Now we fix such J,W,π,ρJ,W,\pi,\rho, and also fix Z⊆[n]∖KZ\subseteq[n]\setminus K. By Lemma 2.8, we have

δr+2,πρ(FK,Z)≥∑T⊆Wδr,π((FK,Z)J,T)−∣{S∈Br(π):∣S∣=t,RS(FK,Z)=2W}∣.\delta_{r+2,\pi\rho}(\mathcal{F}_{K,Z})\geq\sum_{T\subseteq W}\delta_{r,\pi}((\mathcal{F}_{K,Z})_{J,T})-\left|\left\{S\in B_r(\pi):|S|=t,\mathcal{R}_S(\mathcal{F}_{K,Z})=2^W\right\}\right|.

Summing over Z⊆[n]∖KZ\subseteq[n]\setminus K and averaging over J,W,π,ρJ,W,\pi,\rho, we have f1≥f2−f3f_1\geq f_2-f_3, where

f1=1(nr)(n−r2)r!2!∑J∈([n]r)∑W∈([n]∖J2)∑π∑ρ∑Z⊆[n]∖Kδr+2,πρ(FK,Z),f_1=\frac{1}{\binom{n}{r}\binom{n-r}{2}r!2!}\sum_{J\in\binom{[n]}{r}}\sum_{W\in\binom{[n]\setminus J}{2}}\sum_{\pi}\sum_{\rho}\sum_{Z\subseteq[n]\setminus K}\delta_{r+2,\pi\rho}(\mathcal{F}_{K,Z}),
f2=1(nr)(n−r2)r!2!∑J∈([n]r)∑W∈([n]∖J2)∑π∑ρ∑Z⊆[n]∖K∑T⊆Wδr,π((FK,Z)J,T),f_2=\frac{1}{\binom{n}{r}\binom{n-r}{2}r!2!}\sum_{J\in\binom{[n]}{r}}\sum_{W\in\binom{[n]\setminus J}{2}}\sum_{\pi}\sum_{\rho}\sum_{Z\subseteq[n]\setminus K}\sum_{T\subseteq W}\delta_{r,\pi}((\mathcal{F}_{K,Z})_{J,T}),
f3=1(nr)(n−r2)r!2!∑J∈([n]r)∑W∈([n]∖J2)∑π∑ρ∑Z⊆[n]∖K∣{S∈Br(π):∣S∣=t,RS(FK,Z)=2W}∣.f_3=\frac{1}{\binom{n}{r}\binom{n-r}{2}r!2!}\sum_{J\in\binom{[n]}{r}}\sum_{W\in\binom{[n]\setminus J}{2}}\sum_{\pi}\sum_{\rho}\sum_{Z\subseteq[n]\setminus K}\left|\left\{S\in B_r(\pi):|S|=t,\mathcal{R}_S(\mathcal{F}_{K,Z})=2^W\right\}\right|.

Then

f1=1(nr+2)(r+2)!∑K∈([n]r+2)∑σ∑Z⊆[n]∖Kδr+2,σ(FK,Z)=1(nr+2)∑K∈([n]r+2)∑Z⊆[n]∖Kδ‾r+2(FK,Z)=αr+2.\begin{aligned} f_1=\frac{1}{\binom{n}{r+2}(r+2)!}\sum_{K\in\binom{[n]}{r+2}}\sum_{\sigma}\sum_{Z\subseteq[n]\setminus K}\delta_{r+2,\sigma}(\mathcal{F}_{K,Z}) \\ &=\frac{1}{\binom{n}{r+2}}\sum_{K\in\binom{[n]}{r+2}}\sum_{Z\subseteq[n]\setminus K}\overline{\delta}_{r+2}(\mathcal{F}_{K,Z})=\alpha_{r+2}. \end{aligned}

Note that (FK,Z)J,T={A⊆J:A∪T∪Z∈F}=FJ,Z∪T(\mathcal{F}_{K,Z})_{J,T}=\{A\subseteq J:A\cup T\cup Z\in\mathcal{F}\}=\mathcal{F}_{J,Z\cup T}, so we have

f2=1(nr+2)(r+2)!∑J∈([n]r)∑W∈([n]∖J2)∑π∑ρ∑Z⊆[n]∖K∑T⊆Wδr,π(FJ,Z∪T).f_2=\frac{1}{\binom{n}{r+2}(r+2)!}\sum_{J\in\binom{[n]}{r}}\sum_{W\in\binom{[n]\setminus J}{2}}\sum_{\pi}\sum_{\rho}\sum_{Z\subseteq[n]\setminus K}\sum_{T\subseteq W}\delta_{r,\pi}(\mathcal{F}_{J,Z\cup T}).

Since every U⊆[n]∖JU\subseteq[n]\setminus J has a unique decomposition U=Z∪TU=Z\cup T, with Z=U∖KZ=U\setminus K and T=U∩(K∖J)T=U\cap(K\setminus J), we have

f2=1(nr+2)(r+2)!∑J∈([n]r)∑W∈([n]∖J2)∑π∑ρ∑U⊆[n]∖Jδr,π(FJ,U).f_2=\frac{1}{\binom{n}{r+2}(r+2)!}\sum_{J\in\binom{[n]}{r}}\sum_{W\in\binom{[n]\setminus J}{2}}\sum_{\pi}\sum_{\rho}\sum_{U\subseteq[n]\setminus J}\delta_{r,\pi}(\mathcal{F}_{J,U}).

Note that δr,π(FJ,U)\delta_{r,\pi}(\mathcal{F}_{J,U}) is independent of the choice of WW and ρ\rho, so we have

f2=(n−r2)2!r!(nr+2)(r+2)!∑J∈([n]r)∑U⊆[n]∖J(∑π1r!δr,π(FJ,U))=1(nr)∑J∈([n]r)∑U⊆[n]∖Jδ‾r(FJ,U)=αr.\begin{aligned} f_2=\frac{\binom{n-r}{2}2!r!}{\binom{n}{r+2}(r+2)!}\sum_{J\in\binom{[n]}{r}}\sum_{U\subseteq[n]\setminus J}\left(\sum_{\pi}\frac{1}{r!}\delta_{r,\pi}(\mathcal{F}_{J,U})\right) \\ &=\frac{1}{\binom{n}{r}}\sum_{J\in\binom{[n]}{r}}\sum_{U\subseteq[n]\setminus J}\overline{\delta}_r(\mathcal{F}_{J,U})=\alpha_r. \end{aligned}

Now we compute f3f_3. We firstly prove that RS(FK,Z)=2W\mathcal{R}_S(\mathcal{F}_{K,Z})=2^W if and only if Q(Z,W)⊆RJ,SQ(Z,W)\subseteq\mathcal{R}_{J,S}. Recall the definition of RS(A)\mathcal{R}_S(\mathcal{A}) in Lemma 2.8: RS(A)={T⊆W:S∈Sh⁡(AJ,T)}\mathcal{R}_S(\mathcal{A})=\{T\subseteq W:S\in\operatorname{Sh}(\mathcal{A}_{J,T})\} for S⊆JS\subseteq J. Note we have (FK,Z)J,T=FJ,T∪Z(\mathcal{F}_{K,Z})_{J,T}=\mathcal{F}_{J,T\cup Z}, so RS(FK,Z)=2W\mathcal{R}_S(\mathcal{F}_{K,Z})=2^W if and only if S∈Sh⁡((FK,Z)J,T)=Sh⁡(FJ,T∪Z)S\in\operatorname{Sh}((\mathcal{F}_{K,Z})_{J,T})=\operatorname{Sh}(\mathcal{F}_{J,T\cup Z}) for every T⊆WT\subseteq W, which means T∪Z∈RJ,ST\cup Z\in\mathcal{R}_{J,S}. Recall that a coordinate square Q(Z,W)Q(Z,W) is defined as Q(Z,W)={Z∪T:T⊆W}Q(Z,W)=\{Z\cup T:T\subseteq W\}. Hence RS(FK,Z)=2W\mathcal{R}_S(\mathcal{F}_{K,Z})=2^W if and only if Q(Z,W)⊆RJ,SQ(Z,W)\subseteq\mathcal{R}_{J,S}. So we have

f3=1(nr)(n−r2)r!2!∑J∈([n]r)∑W∈([n]∖J2)∑π∑ρ∑Z⊆[n]∖K∑S∈Br(π)∣S∣=t1{Q(Z,W)⊆RJ,S}.f_3=\frac{1}{\binom{n}{r}\binom{n-r}{2}r!2!}\sum_{J\in\binom{[n]}{r}}\sum_{W\in\binom{[n]\setminus J}{2}}\sum_{\pi}\sum_{\rho}\sum_{Z\subseteq[n]\setminus K}\sum_{\substack{S\in B_r(\pi)\\ |S|=t}}\mathbf{1}_{\{Q(Z,W)\subseteq\mathcal{R}_{J,S}\}}.

Now we fix J∈([n]r)J \in\binom{[n]}{r} and S∈(Jt)S \in\binom{J}{t}. For every W∈([n]∖J2)W \in\binom{[n]\setminus J}{2} and Z⊆[n]∖(J∪W)Z \subseteq[n]\setminus(J\cup W), we have a coordinate square Q(Z,W)Q(Z,W). So

∑W∈([n]∖J2)∑Z⊆[n]∖(J∪W)1{Q(Z,W)⊆RJ,S}=c2(RJ,S).\sum_{W\in\binom{[n]\setminus J}{2}}\sum_{Z\subseteq[n]\setminus(J\cup W)}\mathbf{1}\{Q(Z,W)\subseteq\mathcal{R}_{J,S}\}=c_2(\mathcal{R}_{J,S}).

Note that we choose π\pi uniformly, so by Lemma 2.6, we have P(S∈Br(π))=br,t/(rt)\mathbb{P}(S\in B_r(\pi))=b_{r,t}/\binom{r}{t}. Also note that c2(RJ,S)c_2(\mathcal{R}_{J,S}) is independent of the choice of ρ\rho, so we have

f3=br,t(nr)(n−r2)(rt)∑J∈([n]r)∑S∈(Jt)c2(RJ,S).f_3=\frac{b_{r,t}}{\binom{n}{r}\binom{n-r}{2}\binom{r}{t}}\sum_{J\in\binom{[n]}{r}}\sum_{S\in\binom{J}{t}}c_2(\mathcal{R}_{J,S}).

By Lemma 2.11, we have

f3≤br,t(d−t2)(rt)(nr)(n−r2)(rt)∑J∈([n]r)∑U⊆[n]∖Jer(FJ,U).f_3\leq\frac{b_{r,t}\binom{d-t}{2}\binom{r}{t}}{\binom{n}{r}\binom{n-r}{2}\binom{r}{t}}\sum_{J\in\binom{[n]}{r}}\sum_{U\subseteq[n]\setminus J}e_r(\mathcal{F}_{J,U}).

So we have f3≤ar(n,d)βrf_3\leq a_r(n,d)\beta_r, hence

αr+2≥αr−ar(n,d)βr.(6)\alpha_{r+2}\geq\alpha_r-a_r(n,d)\beta_r. \tag*{(6)}

□\square

Even if we know αr≥0\alpha_r\geq0, we cannot get αr+2≥0\alpha_{r+2}\geq0 only by Proposition 2.13. Therefore we need to dig out more information between β\beta and α\alpha. Before this, we need several auxiliary results. We first show the whole family F\mathcal{F} is strongly influenced by the restricted family FJ,U\mathcal{F}_{J,U}.

Lemma 2.14. Let 3≤p≤m3\leq p\leq m, and let A⊆2[m]\mathcal{A}\subseteq2^{[m]} be a Sperner family. Suppose that AJ,U\mathcal{A}_{J,U} is elementary for every J∈([m]p)J\in\binom{[m]}{p} and every U⊆[m]∖JU\subseteq[m]\setminus J. Then either A\mathcal{A} is elementary, or ∣X△Y∣>p|X\triangle Y|>p for all distinct X,Y∈AX,Y\in\mathcal{A}.

Proof of Lemma 2.14. Induction on mm. If m=pm=p and there exist two distinct sets X,Y∈AX,Y\in\mathcal{A} such that ∣X△Y∣≤p|X\triangle Y|\leq p, then A\mathcal{A} must be a complete layer. In fact, in this case, JJ can only be [m][m], which means A\mathcal{A} is elementary. Since A\mathcal{A} has at least two sets, A\mathcal{A} must be a complete ss layer with 1≤s≤m−11\leq s\leq m-1.

Assume that the statement holds for mm with m≥pm\geq p. We prove it for m+1m+1. If there exist two distinct sets X,Y∈AX,Y\in\mathcal{A} such that ∣X△Y∣≤p|X\triangle Y|\leq p, then there exists at least one coordinate not contained in X△YX\triangle Y. So we may suppose ii is not contained in either XX or YY for some ii. Indeed, if we can not take such ii, then there exists jj, such that j∈X∩Yj\in X\cap Y. So we can take complements for every set in A\mathcal{A}. Note taking complements preserves the hypothesis, since the complement in JJ of an elementary restricted family is again elementary.

Without loss of generality, we may further assume that the coordinate ii we take is m+1m+1. So X,Y∈2[m]X,Y\in2^{[m]} and ∣X△Y∣≤p|X\triangle Y|\leq p. By the induction hypothesis, we know that the subfamily of A\mathcal{A} consisting of all sets not containing m+1m+1 is a complete ss layer on the ground set [m][m] with 1≤s≤m−11\leq s\leq m-1. For any B∈([m]s)B\in\binom{[m]}{s}, B∪{m+1}B\cup\{m+1\} is also contained in A\mathcal{A}. In fact, since 1≤s≤m−11\leq s\leq m-1, we can take two distinct coordinates a,ba,b outside B∪{m+1}B\cup\{m+1\}. Note p≥3p\geq3, so we can choose a set JJ of size pp such that JJ contains {a,b,m+1}\{a,b,m+1\}. We take the outside part to be B∖JB\setminus J. Then this restricted family contains at least two members and hence it must be a complete layer, which means B∪{m+1}B\cup\{m+1\} must be contained in A\mathcal{A}. So A\mathcal{A} contains a complete ss layer on the ground set [m+1][m+1]. Note A\mathcal{A} is a Sperner family, so no other set can be contained in A\mathcal{A}. Hence A\mathcal{A} is a complete ss layer on the ground set [m+1][m+1] with 1≤s≤m−11\leq s\leq m-1.

□\square

We next compare δˉq(A)\bar{\delta}_q(\mathcal{A}) with the number of exceptional restricted families AJ,U\mathcal{A}_{J,U} for ∣J∣=p|J|=p.

Lemma 2.15. Let p,qp,q be odd with 3≤p<q≤2p−13\leq p<q\leq2p-1. Every Sperner family A⊆2[q]\mathcal{A}\subseteq2^{[q]} satisfies

eq(A)≤δˉq(A)+(q(q−1)/2)∑J∈([q]p)∑U⊆[q]∖Jep(AJ,U).e_q(\mathcal{A})\leq\bar{\delta}_q(\mathcal{A})+\binom{q}{(q-1)/2}\sum_{J\in\binom{[q]}{p}}\sum_{U\subseteq[q]\setminus J}e_p(\mathcal{A}_{J,U}).

Proof of Lemma 2.15. If there exists a restricted family AJ,U\mathcal{A}_{J,U} with ∣J∣=p|J|=p that is exceptional, then the sum in the statement is at least one. Note A\mathcal{A} is nonempty and hence shatters the empty set. So by (2), we have δˉq(A)≥1−∣A∣\bar{\delta}_q(\mathcal{A}) \ge1-|\mathcal{A}|. Using Lemma 2.1, we have ∣A∣≤(q(q−1)/2)|\mathcal{A}| \le\binom{q}{(q-1)/2}, so the right side of the stated inequality is at least 1−∣A∣+(q(q−1)/2)≥1≥eq(A)1-|\mathcal{A}|+\binom{q}{(q-1)/2} \ge1 \ge e_q(\mathcal{A}).

Now we suppose every restricted family AJ,U\mathcal{A}_{J,U} with ∣J∣=p|J|=p is elementary. If A\mathcal{A} is elementary, then eq(A)=δˉq(A)=0e_q(\mathcal{A})=\bar{\delta}_q(\mathcal{A})=0 by Lemma 2.7. If A\mathcal{A} is exceptional, then ∣A∣≥2|\mathcal{A}|\ge2 and Lemma 2.14 gives ∣A△B∣≥p+1|A\mathbin{\triangle}B|\ge p+1 for all distinct A,B∈AA,B\in\mathcal{A}.

Claim 2.16. ∣A∣≤23(p+1)|\mathcal{A}|\le\frac{2}{3}(p+1).

Proof of claim. Choose A,BA,B independently and uniformly from A\mathcal{A}, allowing A=BA=B. For a fixed coordinate, let θ\theta be the proportion of members of A\mathcal{A} containing it. By independence, AA and BB differ at this coordinate with probability 2θ(1−θ)≤122\theta(1-\theta)\le\frac{1}{2}. Summing over the qq coordinates gives E∣A△B∣≤q2\mathbb{E}|A\mathbin{\triangle}B|\le\frac{q}{2}. On the other hand, P(A=B)=1∣A∣\mathbb{P}(A=B)=\frac{1}{|\mathcal{A}|}, and ∣A△B∣≥p+1|A\mathbin{\triangle}B|\ge p+1 whenever A≠BA\ne B. Thus (p+1)(1−1∣A∣)≤E∣A△B∣≤q2(p+1)\left(1-\frac{1}{|\mathcal{A}|}\right)\le\mathbb{E}|A\mathbin{\triangle}B|\le\frac{q}{2}. Since 2(p+1)−q≥32(p+1)-q\ge3, we have ∣A∣≤2(p+1)2(p+1)−q≤23(p+1)|\mathcal{A}|\le\frac{2(p+1)}{2(p+1)-q}\le\frac{2}{3}(p+1).

Fix distinct A,B∈AA,B\in\mathcal{A}. For each i∈A△Bi\in A\mathbin{\triangle}B, one of AA and BB contains ii and the other does not, so {i}\{i\} is shattered by A\mathcal{A}. Thus A\mathcal{A} shatters at least p+1p+1 singletons and the empty set. Note bq,0=1b_{q,0}=1 and bq,1=q−1b_{q,1}=q-1, so we have δˉq(A)≥1+23(p+1)−∣A∣≥1=eq(A)\bar{\delta}_q(\mathcal{A})\ge1+\frac{2}{3}(p+1)-|\mathcal{A}|\ge1=e_q(\mathcal{A}).

For these values of p,qp,q, put cq,p=(q(q−1)/2)(qp)c_{q,p}=\binom{q}{(q-1)/2}\binom{q}{p}. Summing Lemma 2.15 over the restricted families gives the following inequality.

Proposition 2.17. For odd p,qp,q with 3≤p<q≤min⁡(2p−1,n)3\le p<q\le\min(2p-1,n), we have

βq≤αq+cq,pβp.\beta_q\le\alpha_q+c_{q,p}\beta_p.

Proof of Proposition 2.17. Fix K∈([n]q)K\in\binom{[n]}{q} and Z⊆[n]∖KZ\subseteq[n]\setminus K. For J∈(Kp)J\in\binom{K}{p} and T⊆K∖JT\subseteq K\setminus J, we have (FK,Z)J,T={A⊆J:A∪T∪Z∈F}=FJ,Z∪T(\mathcal{F}_{K,Z})_{J,T}=\{A\subseteq J:A\cup T\cup Z\in\mathcal{F}\}=\mathcal{F}_{J,Z\cup T}. For fixed J⊆KJ\subseteq K, every U⊆[n]∖JU\subseteq[n]\setminus J has a unique decomposition U=Z∪TU=Z\cup T, with Z=U∖KZ=U\setminus K and T=U∩(K∖J)T=U\cap(K\setminus J). Hence we have

∑Z⊆[n]∖K∑T⊆K∖Jep(FJ,Z∪T)=∑U⊆[n]∖Jep(FJ,U).\sum_{Z\subseteq[n]\setminus K}\sum_{T\subseteq K\setminus J}e_p(\mathcal{F}_{J,Z\cup T})=\sum_{U\subseteq[n]\setminus J}e_p(\mathcal{F}_{J,U}).

Applying Lemma 2.15 to FK,Z\mathcal{F}_{K,Z}, we have

eq(FK,Z)≤δˉq(FK,Z)+(q(q−1)/2)∑J∈(Kp)∑T⊆K∖Jep((FK,Z)J,T).e_q(\mathcal{F}_{K,Z})\le\bar{\delta}_q(\mathcal{F}_{K,Z})+\binom{q}{(q-1)/2}\sum_{J\in\binom{K}{p}}\sum_{T\subseteq K\setminus J}e_p((\mathcal{F}_{K,Z})_{J,T}).

Summing over Z⊆[n]∖KZ\subseteq[n]\setminus K and averaging over K∈([n]q)K\in\binom{[n]}{q}, we have

βq≤αq+(q(q−1)/2)(np)(nq)(np)1(nq)∑K∈([n]q)∑Z⊆[n]∖K∑J∈(Kp)∑T⊆K∖Jep((FK,Z)J,T)=αq+(q(q−1)/2)(np)(nq)(np)∑K∈([n]q)∑J∈(Kp)∑U⊆[n]∖Jep(FJ,U).\begin{aligned} \beta_q\le\alpha_q+\frac{\binom{q}{(q-1)/2}\binom{n}{p}}{\binom{n}{q}\binom{n}{p}}\frac{1}{\binom{n}{q}}\sum_{K\in\binom{[n]}{q}}\sum_{Z\subseteq[n]\setminus K}\sum_{J\in\binom{K}{p}}\sum_{T\subseteq K\setminus J}e_p((\mathcal{F}_{K,Z})_{J,T}) \\ &=\alpha_q+\frac{\binom{q}{(q-1)/2}\binom{n}{p}}{\binom{n}{q}\binom{n}{p}}\sum_{K\in\binom{[n]}{q}}\sum_{J\in\binom{K}{p}}\sum_{U\subseteq[n]\setminus J}e_p(\mathcal{F}_{J,U}). \end{aligned}

Fix JJ. Then there are (n−pq−p)\binom{n-p}{q-p} sets K∈([n]q)K\in\binom{[n]}{q} that contain JJ. Note (np)(n−pq−p)=(nq)(qp)\binom{n}{p}\binom{n-p}{q-p}=\binom{n}{q}\binom{q}{p}, so we have

βq≤αq+(q(q−1)/2)(np)(n−pq−p)(nq)βp=αq+cq,pβp.(7)\beta_q\le\alpha_q+\frac{\binom{q}{(q-1)/2}\binom{n}{p}\binom{n-p}{q-p}}{\binom{n}{q}}\beta_p=\alpha_q+c_{q,p}\beta_p. \tag*{(7)}

We now suppose that nn is sufficiently large in terms of dd. Combining (6) and (7), we will prove that αq≥0\alpha_q \ge0 and βq≤(q−3)6⋅24q−16αq\beta_q \le(q-3)^6 \cdot2^{4q-16}\alpha_q for every odd 5≤q≤2d−15 \le q \le2d-1.

Proposition 2.18. For every integer d≥3d \ge3, put n0(d)=d10⋅25d−10n_0(d)=d^{10}\cdot2^{5d-10}. Then for every n≥n0(d)n\ge n_0(d) and every odd qq with 5≤q≤2d−15\le q\le2d-1, we have αq≥0\alpha_q\ge0 and βq≤(q−3)6⋅24q−16αq\beta_q\le(q-3)^6\cdot2^{4q-16}\alpha_q.

Proof of Proposition 2.18. For any fixed odd qq with 5≤q≤2d−15\le q\le2d-1, put p=2⌈q+14⌉+1p=2\left\lceil\frac{q+1}{4}\right\rceil+1. Then pp is the smallest odd integer at least q+12\frac{q+1}{2}. For fixed dd and any odd rr with p≤r<qp\le r<q, ar(n,d)a_r(n,d) tends to zero as nn tends to infinity. For this fixed dd, if n≥d10⋅25d−10n\ge d^{10}\cdot2^{5d-10}, then for any such p,q,rp,q,r, we have

(1+22q−6⋅p6⋅24p−16)∑p≤r<qr oddar(n,d)≤12.(8)\left(1+2^{2q-6}\cdot p^6\cdot2^{4p-16}\right) \sum_{\substack{p\le r<q\\r\ \mathrm{odd}}}a_r(n,d)\le\frac{1}{2}. \tag*{(8)}

In fact, recall that ar(n,d)=br,r−12(d−r−12n−r2)(n2)a_r(n,d)=\frac{b_{r,\frac{r-1}{2}}\binom{d-\frac{r-1}{2}}{\frac{n-r}{2}}}{\binom{n}{2}} and br,r−12=(rr−12)−(rr−32)b_{r,\frac{r-1}{2}}=\binom{r}{\frac{r-1}{2}}-\binom{r}{\frac{r-3}{2}}. Since 5≤q≤2d−15\le q\le2d-1 and p=2⌈q+14⌉+1p=2\left\lceil\frac{q+1}{4}\right\rceil+1, we have 3≤p≤q+323\le p\le\frac{q+3}{2} and q+32≤d+1\frac{q+3}{2}\le d+1. Hence we have r≤q−2≤2d−3r\le q-2\le2d-3 and 1≤r−12≤d−21\le\frac{r-1}{2}\le d-2.

Since 2(rr−12)≤2r2\binom{r}{\frac{r-1}{2}}\le2^r, we have 0≤br,r−12≤(rr−12)≤2r−1≤22d−40\le b_{r,\frac{r-1}{2}}\le\binom{r}{\frac{r-1}{2}}\le2^{r-1}\le2^{2d-4}. We also have (n−r2)≥n28\binom{n-r}{2}\ge\frac{n^2}{8} since n≥d10⋅25d−10≥4dn\ge d^{10}\cdot2^{5d-10}\ge4d and r≤2d−3r\le2d-3. Note (d−r−122)≤d22\binom{d-\frac{r-1}{2}}{2}\le\frac{d^2}{2}, so for any odd rr with p≤r<qp\le r<q, we have

ar(n,d)≤22d−4⋅d2/2n2/8=d2⋅22d−2n2.(9)a_r(n,d)\le\frac{2^{2d-4}\cdot d^2/2}{n^2/8}=\frac{d^2\cdot2^{2d-2}}{n^2}. \tag*{(9)}

Since q≥5q\ge5 and p≥3p\ge3, we have 22q−6⋅p6⋅24p−16=p6⋅22q+4p−22≥12^{2q-6}\cdot p^6\cdot2^{4p-16}=p^6\cdot2^{2q+4p-22}\ge1. Note q≤2d−1q\le2d-1 and p≤d+1p\le d+1, so we have

1+22q−6⋅p6⋅24p−16≤22q−5⋅p6⋅24p−16≤(d+1)6⋅28d−19.(10)1+2^{2q-6}\cdot p^6\cdot2^{4p-16}\le2^{2q-5}\cdot p^6\cdot2^{4p-16}\le(d+1)^6\cdot2^{8d-19}. \tag*{(10)}

Combining (9) and (10), we have (1+22q−6⋅p6⋅24p−16)∑p≤r<qr oddar(n,d)≤d3(d+1)6⋅210d−21n2\left(1+2^{2q-6}\cdot p^6\cdot2^{4p-16}\right)\sum_{\substack{p\le r<q\\r\ \mathrm{odd}}}a_r(n,d)\le\frac{d^3(d+1)^6\cdot2^{10d-21}}{n^2}. So we get (8) when n≥d10⋅25d−10n\ge d^{10}\cdot2^{5d-10}. In particular, 0≤ar(n,d)≤10\le a_r(n,d)\le1 for every odd rr with p≤r<qp\le r<q when n≥d10⋅25d−10n\ge d^{10}\cdot2^{5d-10}.

Now we suppose d≥3d\ge3 and n≥d10⋅25d−10n\ge d^{10}\cdot2^{5d-10} are both fixed. Suppose αp≥0\alpha_p\ge0 and βp≤(p−3)6⋅24p−16αp\beta_p\le(p-3)^6\cdot2^{4p-16}\alpha_p if p≥5p\ge5. Note β3≤3α3\beta_3\le3\alpha_3 by Lemma 2.7, so in any case, we always have βp≤p6⋅24p−16αp\beta_p\le p^6\cdot2^{4p-16}\alpha_p.

Claim 2.19. αq≥12αp\alpha_q\ge\frac{1}{2}\alpha_p.

Proof of claim. Write ar=ar(n,d)a_r=a_r(n,d). Recall that cr,p=(rr−1/2(rp))c_{r,p}=\binom{\frac{r}{r-1/2}}{\binom{r}{p}} [sic], so for any odd rr with p<r<qp<r<q, we have cr,p≤22r−2≤22q−6c_{r,p}\le2^{2r-2}\le2^{2q-6} and hence have βr≤αr+22q−6βp\beta_r\le\alpha_r+2^{2q-6}\beta_p by (7). We also have βp≤αp+22q−6βp\beta_p\le\alpha_p+2^{2q-6}\beta_p since αp,βp≥0\alpha_p,\beta_p\ge0 and 22q−6≥12^{2q-6}\ge1. Substituting this inequality into (6), we have αr+2+22q−6βp≥(1−ar)(αr+22q−6βp)\alpha_{r+2}+2^{2q-6}\beta_p\ge(1-a_r)(\alpha_r+2^{2q-6}\beta_p). Since 0≤ar≤10\le a_r\le1 and αp+22q−6βp≥0\alpha_p+2^{2q-6}\beta_p\ge0, we have

αq+22q−6βp≥(∏p≤r<qr odd(1−ar))(αp+22q−6βp).\alpha_q+2^{2q-6}\beta_p\ge\left(\prod_{\substack{p\le r<q\\r\ \mathrm{odd}}}(1-a_r)\right)(\alpha_p+2^{2q-6}\beta_p).

Using ∏p≤r<qr odd(1−ar)≥1−∑p≤r<qr oddar\prod_{\substack{p\le r<q\\r\ \mathrm{odd}}}(1-a_r)\ge1-\sum_{\substack{p\le r<q\\r\ \mathrm{odd}}}a_r, we have αq≥αp−(αp+22q−6βp)∑p≤r<qr oddar\alpha_q\ge\alpha_p-(\alpha_p+2^{2q-6}\beta_p)\sum_{\substack{p\le r<q\\r\ \mathrm{odd}}}a_r. By the hypothesis βp≤p6⋅24p−16αp\beta_p\le p^6\cdot2^{4p-16}\alpha_p, we have

αq≥(1−(1+22q−6⋅p6⋅24p−16)∑p≤r<qr oddar(n,d))αp.\alpha_q\ge\left(1-\left(1+2^{2q-6}\cdot p^6\cdot2^{4p-16}\right)\sum_{\substack{p\le r<q\\r\ \mathrm{odd}}}a_r(n,d)\right)\alpha_p.

By (8), we have αq≥12αp\alpha_q\ge\frac{1}{2}\alpha_p. ■

Since αp≥0\alpha_p \ge0 and αq≥12αp\alpha_q \ge\frac{1}{2}\alpha_p, we have αq≥0\alpha_q \ge0. On the other hand, using (7), we have βq≤αq+cq,pβp\beta_q \le\alpha_q+c_{q,p}\beta_p.

If q=5q=5, then p=3p=3 and c5,3=100c_{5,3}=100. Note we have α3≥0\alpha_3 \ge0 and β3≤3α3\beta_3 \le3\alpha_3 by Lemma 2.7. Using β3≤3α3\beta_3 \le3\alpha_3 and α5≥12α3\alpha_5 \ge\frac{1}{2}\alpha_3, we have β5≤α5+100β3≤601α5≤210α5\beta_5 \le\alpha_5+100\beta_3 \le601\alpha_5 \le2^{10}\alpha_5, as required. If q≥7q \ge7, then p≥5p \ge5. Since βp≤(p−3)6⋅24p−16αp\beta_p \le(p-3)^6\cdot2^{4p-16}\alpha_p and αp≤2αq\alpha_p \le2\alpha_q, we have βq≤(1+2cq,p⋅(p−3)6⋅24p−16)αq\beta_q \le(1+2c_{q,p}\cdot(p-3)^6\cdot2^{4p-16})\alpha_q. Note that q−3≥2(p−3)q-3\ge2(p-3) and p≤q+32p\le\frac{q+3}{2}, so (q−3)6⋅24q−16(p−3)6⋅24p−16≥26+4(q−p)≥22q\frac{(q-3)^6\cdot2^{4q-16}}{(p-3)^6\cdot2^{4p-16}}\ge2^{6+4(q-p)}\ge2^{2q}. Also note that cq,p≤22q−2c_{q,p}\le2^{2q-2} and cq,p⋅(p−3)6⋅24p−16≥1c_{q,p}\cdot(p-3)^6\cdot2^{4p-16}\ge1, so we have

1+2cq,p⋅(p−3)6⋅24p−16≤3cq,p⋅(p−3)6⋅24p−161+2c_{q,p}\cdot(p-3)^6\cdot2^{4p-16}\le3c_{q,p}\cdot(p-3)^6\cdot2^{4p-16}
≤22q⋅(p−3)6⋅24p−16≤(q−3)6⋅24q−16,\begin{aligned} \le2^{2q}\cdot(p-3)^6\cdot2^{4p-16} \\ &\le(q-3)^6\cdot2^{4q-16}, \end{aligned}

which means βq≤(q−3)6⋅24q−16αq\beta_q\le(q-3)^6\cdot2^{4q-16}\alpha_q.

For every odd q≥5q\ge5, p=2⌈q+14⌉+1p=2\left\lceil\frac{q+1}{4}\right\rceil+1 is the smallest odd integer at least q+12\frac{q+1}{2}, and hence 2⌈p+14⌉+12\left\lceil\frac{p+1}{4}\right\rceil+1 is the smallest odd integer at least p+12\frac{p+1}{2}. Repeating this finitely many times, we always get 3. By Lemma 2.7, we have α3≥0\alpha_3\ge0 and β3≤3α3\beta_3\le3\alpha_3. So, by induction, if dd is fixed and n≥d10⋅25d−10n\ge d^{10}\cdot2^{5d-10}, then for every odd qq with 5≤q≤2d−15\le q\le2d-1, we have αq≥0\alpha_q\ge0 and βq≤(q−3)6⋅24q−16αq\beta_q\le(q-3)^6\cdot2^{4q-16}\alpha_q.

It is enough to prove that α2d−1(F)≥0\alpha_{2d-1}(\mathcal{F})\ge0 to get ∣F∣≤(nd)|\mathcal{F}|\le\binom{n}{d}. 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≤(nd)−∣F∣0\le\alpha_{2d-1}\le\binom{n}{d}-|\mathcal{F}| when n≥d10⋅25d−10n\ge d^{10}\cdot2^{5d-10}. This proves the bound.

Now we suppose that ∣F∣=(nd)|\mathcal{F}|=\binom{n}{d}. Then by Proposition 2.18, we know that α2d−1=0\alpha_{2d-1}=0 means that β2d−1=0\beta_{2d-1}=0. Note that β2d−1\beta_{2d-1} is the average number of exceptional restricted families, so β2d−1=0\beta_{2d-1}=0 means that every restricted family is elementary. In other words, for any J∈([n]2d−1)J\in\binom{[n]}{2d-1} and any U⊆[n]∖JU\subseteq[n]\setminus J, FJ,U\mathcal{F}_{J,U} is elementary.

If F\mathcal{F} is exceptional, then F\mathcal{F} has at least two members. By Lemma 2.14, for any two distinct sets X,Y∈FX,Y\in\mathcal{F}, we have ∣X△Y∣>2d−1|X\mathbin{\triangle}Y|>2d-1. Now we fix J∈([n]2d−1)J\in\binom{[n]}{2d-1} and denote H={A∖J:A∈F}⊆2[n]∖J\mathcal{H}=\{A\setminus J:A\in\mathcal{F}\}\subseteq2^{[n]\setminus J}. Note that if A∖J=B∖JA\setminus J=B\setminus J for some A,B∈FA,B\in\mathcal{F}, then we must have A=BA=B. In fact, if A≠BA\ne B and A∖J=B∖JA\setminus J=B\setminus J, then ∣A△B∣>2d−1|A\mathbin{\triangle}B|>2d-1 and A△B⊆JA\mathbin{\triangle}B\subseteq J, but ∣J∣=2d−1|J|=2d-1, which is impossible. So we have a bijection between F\mathcal{F} and H\mathcal{H}. Note that H\mathcal{H} is a family on the ground set [n]∖J[n]\setminus J, so any set shattered by H\mathcal{H} can also be shattered by F\mathcal{F}. Hence VCdim⁡(H)≤VCdim⁡(F)≤d\operatorname{VCdim}(\mathcal{H})\le\operatorname{VCdim}(\mathcal{F})\le d. Then by Lemma 2.2, we have ∣H∣≤∑j=0d(n−2d+1j)|\mathcal{H}|\le\sum_{j=0}^{d}\binom{n-2d+1}{j}. Note that b2d−1,0=1b_{2d-1,0}=1 and b2d−1,1=2d−2>0b_{2d-1,1}=2d-2>0, so by Lemma 2.5, we have

(nd)=∑s=0d−1b2d−1,s∑j=0d−s(n−2d+1j)>∑j=0d(n−2d+1j),\binom{n}{d}=\sum_{s=0}^{d-1}b_{2d-1,s}\sum_{j=0}^{d-s}\binom{n-2d+1}{j}>\sum_{j=0}^{d}\binom{n-2d+1}{j},

which contradicts (nd)=∣F∣=∣H∣\binom{n}{d}=|\mathcal{F}|=|\mathcal{H}|.

Hence F\mathcal{F} must be elementary. Note that ∣F∣=(nd)>1|\mathcal{F}|=\binom{n}{d}>1, so it must be a complete ss layer with 1≤s≤n−11\le s\le n-1. Then obviously, ss must be dd or n−dn-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. [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. [2]R. P. Anstee and A. Sali. Sperner families of bounded VC-dimension. Discrete Math., 175(1-3):13–21, 1997.DOI
  3. [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. [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. [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. [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. [7]J. Fox, J. Pach, and A. Suk. Sunflowers in set systems of bounded dimension. Combinatorica, 43(1):187–202, 2023.
  8. [8]P. Frankl. Traces of antichains. Graphs Combin., 5(1):295–299, 1989.DOI
  9. [9]P. Frankl and J. Pach. On disjointly representable sets. Combinatorica, 4(1):39–45, 1984.DOI
  10. [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. [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. [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. [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. [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. [15]D. Mubayi and Y. Zhao. On the VC-dimension of uniform hypergraphs. J. Algebraic Combin., 25(1):101–110, 2007.DOI
  16. [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. [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. [18]N. Sauer. On the density of families of sets. J. Combin. Theory Ser. A, 13:145–147, 1972.DOI
  19. [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. [20]E. Sperner. Ein Satz über Untermengen einer endlichen Menge. Math. Z., 27(1):544–548, 1928.DOI
  21. [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. [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. [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. [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. [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. [26]X. Zhao and G. Ge. Recursive lifting beyond the Ahlswede–Khachatriian construction, 2026. arXiv:2607.04858.arxiv.org/abs/2607.04858

Paper details

vlnc:W_arw9vpe3
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents