# Shattering-Extremal Set Systems of Small VC-Dimension

Authors: Tamás Mészáros; Lajos Rónyai
Journal: ISRN Combinatorics
 (2013)

---

## Abstract

We say that a set systemℱ⊆2[n] shatters a given set S⊆[n] if 2S={F∩S:F∈ℱ}. The Sauer inequality states that in general, a set system ℱ shatters at least |ℱ| sets. Here, we concentrate on the case of equality. A set system is called shattering-extremal if it shatters exactly |ℱ| sets. We characterize shattering extremal set systems of Vapnik-Chervonenkis dimension 1 in terms of their inclusion graphs. Also, from the perspective of extremality, we relate set systems of bounded Vapnik-Chervonenkis dimension to their projections.


---

## Body

## 1. Introduction

Throughout this paper,n will be a positive integer, and the set {1,2,…,n} will be referred to shortly as [n], the power set of it as 2[n], and the family of subsets of size k as ([n]k).The central notion of our study is shattering. We say that a set systemℱ⊆2[n] shatters a given set S⊆[n] if 2S={F∩S:F∈ℱ}. The family of subsets of [n] shattered by ℱ is denoted by Sh(ℱ). The following inequality gives a bound on the size of Sh(ℱ).Proposition 1.
|
Sh
(
ℱ
)
|
≥
|
ℱ
|.The statement was proved by several authors, such as Aharoni and Holzman [1], Pajor [2], Sauer [3], and Shelah [4]. It is often referred to as Sauer inequality. One of the most interesting cases is the case of equality, that is, when the set system ℱ shatters exactly |ℱ| sets. We call such set system shattering extremal or s-extremal for short. Many interesting results have been obtained in connection with these combinatorial objects, among others in [5–9].The Vapnik-Chervonenkis dimension of a set systemℱ⊆2[n], denoted by VC-dim(ℱ), is the maximum cardinality of a set shattered by ℱ. The general task of giving a good description of s-extremal systems seems to be too complex at this point. We restrict therefore our attention to the simplest cases, where the VC-dimension of ℱ is bounded by some fixed natural number t.After the Introduction, in Section2, we first investigate s-extremal set systems of VC-dimension 1 from a graph theoretical point of view. We give a bijection between the family of such set systems on the ground set [n] and trees on n+1 vertices. As a consequence, one can exactly determine the number of such s-extremal set systems. In combinatorics, when considering set systems with a given property, it is a common step to first consider families of some special structure. According to [10], uniform set systems cannot be s-extremal. As a next possibility, set systems from two consecutive layers turn up. In Section 3, we prove that they are just special cases of the previous ones. After this in Section 4, we switch to an algebraic point of view and investigate bases of the polynomial ideals attached to extremal set systems. The main result of Section 5 is a connection between s-extremal set systems of VC-dimension t and their projections. At the end, we propose an open problem and make some concluding remarks.In the paper, we will use the terminology of [11] for graph theoretical notions.


## 2. s-Extremal Set Systems of VC-Dimension 1

Letℱ⊆2[n] be an s-extremal family. Let Gℱ be the labelled Hasse diagram of ℱ considered as a graph, that is, a graph whose vertices are the elements of ℱ, and there is a directed edge going from G to F, labelled with j∈[n] exactly when F=G∪{j}. Gℱ will be called the inclusion graph of ℱ. When representing the elements of ℱ by their characteristic vectors, Gℱ can also be considered as the subgraph in the Hamming graph Hn={0,1}n spanned by the elements corresponding to the sets in ℱ with edges directed and labelled in a natural way. Actually, for the next proposition, we can forget about the directions of the edges, and consider Gℱ as an undirected edge-labelled graph. We further assume that VC-dim(ℱ)≤1. Our aim is to characterize these kinds of s-extremal set systems in terms of their inclusion graph.Proposition 2.
A set systemℱ⊆2[n] is s-extremal and of VC-dimension at most 1 if and only if Gℱ is a tree and all labels on the edges are different.Proof.
For the “only if” direction, suppose thatℱ is s-extremal and VC-dim(ℱ)≤1. According to [10, Theorem 5], we know that Gℱ must be isometrically embedded into Hn (i.e., for any two elements G,F∈ℱ, the distance between G and F is the same in Gℱ and in Hn). This means, in particular, that Gℱ is connected. Next, we prove that all labels on the edges of Gℱ are different. Suppose for contradiction that there are two edges with the same label. Without loss of generality, we may assume that this label is 1. Since there are no two edges going out from a set with the same label, there are sets A,B,C,D∈ℱ, all different, such that 1∈A∩B, C=A∖{1}, and D=B∖{1}. Since A≠B, A∆B(=(A∖B)∪(B∖A)) is nonempty; so, there is an element 1≠a∈A∆B. Without loss of generality, we may assume that a∈A∖B. Now,
(1){1,a}∩A={1,a},{1,a}∩B={1},{1,a}∩C={a},{1,a}∩D=∅.
So,{1,a} is shattered by {A,B,C,D}; consequently, {1,a}∈Sh(ℱ), contradicting the assumption that VC-dim(ℱ)≤1.
To finish with this direction, note that the fact that all labels are different implies thatGℱ is acyclic. Suppose for contradiction that it is not the case, and Gℱ contains a cycle. Pick one edge from this cycle, and let a be its label. On the remaining part of the cycle, there must be another edge labelled with a, since it connects a set containing a with one not containing a. However, this is impossible, since all labels are different. Adding the connectedness of Gℱ, we obtain that it is actually a tree as wanted.
For the reverse direction, suppose thatGℱ is a tree and all labels on the edges are different. It is easily seen that this implies that Gℱ is isometrically embedded into Hn. (Otherwise a path from a set A to B in Gℱ which is not shortest in Hn would contain 2 edges with the same label, corresponding to the addition and deletion of the same element of [n].)
Now, we prove thatVC-dim(ℱ)≤1. Suppose the contrary, namely, that ℱ shatters a set of size 2, for example, {1,2}. This means that there are sets A,B,C,D∈ℱ such that
(2){1,2}∩A={1,2},{1,2}∩B={1},{1,2}∩C={2},{1,2}∩D=∅.
Consider a shortest path inGℱ from A to B. Since 2∈A∖B, this shortest path has to contain an edge labelled with 2. Repeating this argument for C and D, one gets another different (since on a shortest path between A and B every set contains the element 1, on the other hand, on a shortest path between C and D none of the sets does) edge with label 2, which contradicts the assumption that all labels are different.
Now, we calculateSh(ℱ). If i∈[n] is not an edge label, then either all sets F∈ℱ contain i, or none of them does. In particular, {i} is not shattered by ℱ. Thus, Sh(ℱ) consists of ∅ and the sets {i}, where i is an edge label. However, all edge labels are different. So, we get that |Sh(ℱ)|=|E(Gℱ)|+1=|ℱ| (since Gℱ is a tree); that is, ℱ is s-extremal.Letℱ⊆2[n] be an s-extremal family such that supp(ℱ)=∪F∈ℱF=[n] and ∩F∈ℱF=∅. By Proposition 2, to every s-extremal family of VC-dimension 1, one can associate a directed edge-labelled tree Gℱ, all edges having distinct labels. We have seen that Sh(ℱ) consists of ∅ and the sets {i}, where i is an edge label. On the other hand, since ∩F∈ℱF=∅, we also have that Sh(ℱ)={∅}∪{{j}|j∈supp(ℱ)=[n]}. As a consequence the tree must have n edges and thus n+1 vertices; that is, such an s-extremal family has n+1 elements.Now, conversely suppose that we are given a directed edge-labelled treeT on n+1 vertices with n edges, all having different labels. This tree at the same time also defines a set system ℱT={Fv|v∈T}. Take the edges one by one. When considering an edge with label s going from u to v, then for all vertices w closer to v than to u in the undirected tree, put s into Fw. Clearly, T=GℱT, and by the previous proposition, ℱT must be s-extremal.To illustrate this, consider the following example withn=5:
(3)We haveℱT={{1,5},{1,2,5},{2,5},{2,4,5},{2,3,4,5}, {2}}.This gives a bijection between the set of all s-extremal families of VC-dimension 1 and directed edge-labelled trees.Theorem 3.
Letn≥1 be an integer. There is a one-to-one correspondence between s-extremal families ℱ⊆2[n] of Vapnik-Chervonenkis dimension 1 with supp(ℱ)=[n], ∩F∈ℱF=∅, and directed edge-labelled trees on n+1 vertices, all edges having a different label from [n].As a corollary, one can prove the following statement.Corollary 4.
There are2n(n+1)n-2 different s-extremal families ℱ⊆2[n] of Vapnik-Chervonenkis dimension 1 with supp(ℱ)=[n] and ∩F∈ℱF=∅.Proof.
There are(n+1)n-2 different edge-labelled undirected trees on n+1 vertices (see [12]), all edges having a different label from [n], and each of these trees can be directed in 2n ways.Simple examples of s-extremal set systems are downsets, that is, set systemsℱ such that for all i∈[n],i∈F∈ℱ implies that F∖{i}∈ℱ. For  downsets, Sh(ℱ)=ℱ; so, they are obviously s-extremal. One can obtain other examples from downsets using different set system operations, for example, bit flips. For i∈[n], let φi be the ith bit flip; that is, for F∈2[n],
(4)φi(F)={F∖{i}ifi∈F,F∪{i}ifi∉F.Forℱ⊆2[n], set φi(ℱ)={φi(F)∣F∈ℱ}. It is easily seen that s-extremality is invariant with respect to this operation since it keeps the family of shattered sets. However, not all s-extremal set systems can be obtained in this way. For this, note that in terms of the inclusion graph, a bit flip in the ith coordinate corresponds just to reversing the direction of the edge with label i in Gℱ; that is, bit flips preserve the undirected structure of the inclusion graph. Using this we can obtain many s-extremal examples not coming from downsets using bit flips. It is enough to pick a tree that is not a star and consider a set system corresponding to any possible orientation.


## 3. s-Extremal Set Systems from Two Consecutive Layers

For a uniform familyℱ, the graph Gℱ is not connected; hence, ℱ cannot be s-extremal. As a relaxation of uniformity, we consider families which belong to two consecutive layers of 2[n]. The next proposition shows that extremal families among them are actually special cases of the previously studied ones.Proposition 5.
Letℱ⊆([n]k)∪([n]k-1), n≥k≥1, be an s-extremal family of subsets of [n]. Then, one has VC-dim(ℱ)≤1.Proof.
Forn=2, the statement can be verified by an easy case analysis. For n>2, we can do induction on k. For k=1, the statement is just trivial. Now, suppose that k>1 and the result holds for all values smaller than k. We prove that such an s-extremal family cannot shatter a subset of size 2. Suppose the contrary, namely, that ℱ shatters, for example, {1,2}. Let
(5)ℱ0(n)={F∣F∈ℱ,n∉F}⊆([n-1]k)∪([n-1]k-1),ℱ1(n)={F∖{n}∣F∈ℱ,n∈F}⊆([n-1]k-1)∪([n-1]k-2).
Sinceℱ is s-extremal, both ℱ0(n) and ℱ1(n) must be s-extremal (it follows easily from the proof of the Sauer inequality; see, e.g., [5]), and for the shattered sets, we have that
(6)Sh(ℱ)=Sh(ℱ0(n))∪Sh(ℱ1(n))∪{F∪{n}∣F∈Sh(ℱ0(n))∩Sh(ℱ1(n))}.
Sincen>2, by the induction hypothesis, {1,2}∈Sh(ℱ1(n)) cannot hold; thus, we have {1,2}∈Sh(ℱ0(n)). In this way, we constructed an s-extremal family with the same properties but on a smaller ground set. Continuing this we get to an s-extremal family ℱ⊆([k]k)∪([k]k-1) that shatters {1,2}. However, this is easily seen to be impossible, because for any F∈ℱ, we have |F∩{1,2}|≥1. This finishes the proof.Using essentially the same argument, one can prove the following.Proposition 6.
Letℱ⊆([n]k)∪([n]k-1)∪⋯∪([n]k-t+1), n≥k≥t-1≥1, be an s-extremal family of subsets of [n]. Then, one has VC-dim(ℱ)≤t-1.We return now to the situation whenℱ⊆([n]k)∪([n]k-1) for some n≥k≥1 and supp(ℱ)=[n], ∩F∈ℱF=∅. Proposition 2 says in this case that ℱ is s-extremal iff Gℱ (the undirected version) is a tree and all labels on the edges are different. As before, we also have that this tree has n + 1 vertices and n edges. Permuting the labels on the edges corresponds just to a permutation of the ground set; so, if we want to characterize s-extremal set systems up to isomorphism, we can freely omit the labels from the edges.Now, suppose that we are given a treeT on n+1 vertices having n edges. T can also be viewed as a bipartite graph (since it is acyclic and so contains no odd cycles) with partition classes 𝒜,ℬ. Direct all edges from 𝒜 to ℬ, and let ℱ be as before the set system this directed tree just defines. It is easily seen that we have ℱ⊆([n]k)∪([n]k-1), where k=|𝒜|, and using the characterization of s-extremal families, we also get that ℱ is s-extremal. If we swap the role of 𝒜 and ℬ, we get the “dual” set system
(7)ℱ′={[n]∖F∣F∈ℱ}⊆([n]n-k+1)∪([n]n-k),
which is clearly also s-extremal using the same reasoning.Summarizing the preceding discussion, we have the following.Theorem 7.
Up to isomorphism and the operation of taking the “dual” of a set system, there is a one-to-one correspondence between s-extremal set systemsℱ from two consecutive layers on the ground set [n](supp(ℱ)=[n] and ∩F∈ℱF=∅) and trees on n+1 vertices. The bijection is realized via the map ℱ→Gℱ.


## 4. Ideal Bases of s-Extremal Set Systems of VC-Dimension 1

Take a familyℱ⊆2[n], and let 𝔽 be a field. For a set F⊆[n], let vF∈{0,1}n be its characteristic vector; that is, the ith coordinate of vF is 1 exactly when i∈F. One can associate to ℱ a polynomial ideal I(ℱ)⊲𝔽[x1,…,xn], the vanishing ideal of the set of characteristic vectors of the elements of ℱ:
(8)I(ℱ)={f(x1,…,xn)∈𝔽[x1,…,xn]∣f(vF)=0∀F∈ℱ}.I
(
ℱ
) carries a lot of information about the set system. For this connection among ℱ and I(ℱ), see [5, 13].If one is working with polynomial ideals, it is advantageous to have a good ideal basis. Now, we briefly introduce one such class of bases, namely, Gröbner bases. For details, we refer to [14–19].A total order≺ on the monomials composed from variables x1,x2,…,xn is a term order, if 1 is the minimal element of ≺, and ≺ is compatible with multiplication with monomials. One important term order is the lexicographic (lex for short) order. We have x1w1⋯xnwn≺lexx1u1⋯xnun if and only if wi<ui holds for the smallest index i such that wi≠ui. Reordering the variables gives another lex term order.The leading monomiallm(f) of a nonzero polynomial f∈𝔽[x1,…,xn] is the largest monomial (with respect to ≺) which appears with nonzero coefficient in f, when written as the usual linear combination of monomials. We denote the set of all leading monomials of polynomials of a given ideal I⊲𝔽[x1,…,xn] by Lm(I)={lm(f):f∈I}, and we simply call them the leading monomials of I. A monomial is called a standard monomial of I, if it is not a leading monomial of any f∈I. Let Sm(I) denote the set of standard monomials of I. Obviously, a divisor of a standard monomial is again in Sm(I). Standard monomials have some very nice properties; among other things, they form a linear basis of the 𝔽-vector space 𝔽[x1,…,xn]/I.A finite subset𝔾⊆I is a Gröbner basis of I, if for every f∈I, there exists a g∈𝔾 such that lm(g) divides lm(f). It is not hard to verify that 𝔾 is actually a basis of I; that is, 𝔾 generates I as an ideal of 𝔽[x1,…,xn]. It is a fundamental fact that every nonzero ideal I of 𝔽[x1,…,xn] has a Gröbner basis [19, Corollary 1.6.5].Gröbner bases and standard monomials turned out to be very useful when studying s-extremal set systems. Letℱ⊆2[n] be a set system and I(ℱ) its vanishing ideal. Subsets of [n] can be identified with square-free monomials via the map H→∏i∈H‍xi. With this identification in mind, one can prove that Sh(ℱ), viewed as a set of monomials, is just the union of the sets of standard monomials of I(ℱ) for all lexicographic term orders, that is
(9)Sh(ℱ)=⋃lextermorders‍Sm(I(ℱ)).On the other hand, for vanishing ideals, we have that|Sm(I(ℱ))|=|ℱ| for all term orders. These facts altogether result in the fact that a set system ℱ is s-extremal iff the set of standard monomials is the same for all lexicographic term orders. This algebraic characterization of s-extremal set systems leads to an efficient algorithm for testing s-extremality of a set system and offers also the possibility to generalize the notion to arbitrary sets of vectors (for more details and proofs, see [13]).As an application of Proposition2, we determine the Gröbner bases of s-extremal set systems of VC-dimension 1. Suppose that we are given a family ℱ⊆2[n] together with Sh(ℱ). According to [13, Section 4.2], one can construct a Gröbner basis of I(ℱ) as follows. For a pair of sets H⊆S⊆[n], define the following polynomial
(10)fS,H=(∏j∈Hxj)(∏i∈S∖H(xi-1)).
Now, if S∉Sh(ℱ), then there exists a set H⊆S such that there is no set F∈ℱ with F∩S=H. For this set H, we have fS,H∈I(ℱ). If the set S is minimal (i.e., all proper subsets S′ of S are in Sh(ℱ)) and ℱ is s-extremal, then we also have uniqueness for the corresponding H. Moreover, in the s-extremal case, the collection of all these fS,H polynomials corresponding to minimal elements outside Sh(ℱ) together with {xi2-xi,i∈[n]} form a Gröbner basis of I(ℱ) for all term orders. Actually, more is true.Proposition 8 (see [13]).
ℱ
⊆
2
[
n
] is s-extremal iff there are polynomials of the form fS,H, which together with {xi2-xi,i∈[n]} form a Gröbner basis of I(ℱ) for all term orders.If we restrict ourselves to s-extremal set systems ofVC-dimension 1, things become very simple. Suppose that ℱ⊆2[n] is a set system such that VC-dim(ℱ)=1, supp(ℱ)=[n], and ∩F∈ℱF=∅. In this case, Sh(ℱ) is the collection of all sets of size at most 1; so, the minimal sets outside Sh(ℱ) are exactly the sets of size 2. Fix one such set S={α,β}, and consider the 2 edges in the inclusion graph Gℱ labelled by α and β. From Proposition 2, we know that Gℱ is a tree. Consider the unique path connecting the 2 edges. There are 4 possibilities. (i)
The edges are directed towards each other on this path:(11)
In this case, the corresponding set H is ∅; so, fS,H=(xα-1)(xβ-1). Indeed, then, every F∈ℱ contains either α or β.(ii)
The edges are directed away from each other on this path:(12)
In this case, the corresponding set H is {α,β}; so, fS,H=xαxβ. No F∈ℱ contains {α,β}.(iii)
The edges are directed in the same direction towards the edge with labelα on this path:
(13)
In this case, the corresponding set H is {α}; so, fS,H=xα(xβ-1). If α∈F for some F∈ℱ, then β∈F as well.(iv)
The edges are directed in the same direction towards the edge with labelβ on this path:
(14)
Similar to the previous case, H={β}; so, fS,H=(xα-1)xβ.Now, if we haveGℱ, then using the previous case analysis, one can easily compute a Gröbner basis for I(ℱ). If we want just a basis of I(ℱ) and not necessarily a Gröbner basis, we do not need to consider all pairs. Consider 3 consecutive edges in Gℱ, that is, a path of length 3 with labels α,β,andγ:
(15)
They define 3 pairs and, hence, 3 polynomials, fα,β=(xα-εα)(xβ-εβ), fα,γ=(xα-εα)(xγ-εγ), and fβ,γ=(xβ-1+εβ)(xγ-εγ), where εα, εβ, and εγ are 0 or 1 depending on the orientations of the edges (in the above example we have εα=1 and εβ=εγ=0). However,
(16)(xγ-εγ)fα,β-(xα-εα)fβ,γ=(1-2εβ)fα,γ,
where 1-2εβ is either 1 or -1; so, fα,γ is superfluous, since it can be obtained from fα,β and fβ,γ. This means that when constructing a basis of I(ℱ), it is enough to consider only adjacent pairs of edges in Gℱ.


## 5. s-Extremal Set Systems of Bounded  VC-Dimension

The ideas from the previous sections can also be used to step a bit further and obtain results for s-extremal set systems of boundedVC-dimension in general.Let the projection of a set systemℱ⊆2[n] to a set X⊆[n] be
(17)ℱ|X={F∩X∣F∈ℱ}.Note thatX∈Sh(ℱ) iff ℱ|X=2X.The main result of this section considers the projections of a set family from the perspective of extremality.Theorem 9.
Letℱ⊆2[n] be family of VC-dimension t≥1 such that ℱ|X is s-extremal for all 2t+1 element subsets X of [n]. Let
(18)𝒢={H⊆[n]∣H∩X∈ℱ|X=ccH⊆[n]∣forallsetsX⊆[n]ofsize2t+1}.
Then,𝒢 contains ℱ, and is s-extremal and of VC-dimension t. Moreover, if ℱ is s-extremal, then one has 𝒢=ℱ.Before proving Theorem9, we first present some observations about extremal set systems in general.For a set systemℱ⊆2[n] and i∈[n], let ℱ0(i) and ℱ1(i) be as defined previously in Section 3. The downshift operation of a set family ℱ by the element i∈[n] is defined as follows:
(19)Di(ℱ)={F∣F∈ℱ,i∉F}∪{F∣F∈ℱ,i∈F,F∖{i}∈ℱ}c∪{F∖{i}∣F∈ℱ,i∈F,F∖{i}∉ℱ}={F∖{i}∣F∈ℱ}∪{F∣F∈ℱ,i∈F,F∖{i}∈ℱ}.It is not hard to see thatDi preserves s-extremality (e.g., [7, Lemma 1]), and as already noted earlier, if ℱ is s-extremal, then so is ℱj(i) for i∈[n] and j=0,1.For a set systemℱ⊆2[n] and i∈[n], we put
(20)Mi(ℱ)=ℱ0(i)∩ℱ1(i),Ui(ℱ)=ℱ0(i)∪ℱ1(i).Proposition 10.
Suppose that one is given a set systemℱ⊆2[n] and an arbitrary element i∈[n]. Then, if ℱ is s-extremal, then so are Mi(ℱ), Ui(ℱ), and ℱ|X for all X⊆[n]. Actually, for ℱ|X, one has that Sh(ℱ|X)=Sh(ℱ)|X; more precisely, a set Y⊆X is in Sh(ℱ|X) iff it is in Sh(ℱ).Proof.
The following equalities follow easily from the definitions:(21)Mi(ℱ)=ℱ0(i)∩ℱ1(i)=Di(ℱ)1(i),Ui(ℱ)=ℱ0(i)∪ℱ1(i)=Di(ℱ)0(i).
From these it follows that ifℱ is s-extremal, then so are Mi(ℱ) and Ui(ℱ), since we can obtain them from ℱ using operations preserving s-extremality.
Next, note that ifX={x1,…,xm}, then ℱ|X is just Ux1(Ux2(⋯Uxm(ℱ)⋯)); thus, if the original set system is s-extremal, then so is its projected version.
For the second part, we only have to note that for someY⊆X, we have that Y∩(F∩X)=Y∩F for all F⊆[n], and the result follows.We say that a setI⊆[n] is strongly traced or strongly shattered [6, 7] by a set system ℱ⊆2[n] when there is a set B⊆[n]∖I such that
(22)B+2I={B∪H∣H⊆I}⊆ℱ.The collection of all sets strongly traced byℱ is denoted by st(ℱ). It can be shown that |st(ℱ)| is bounded from above by |ℱ| (reverse Sauer inequality, [6, 7]), and a set system is called extremal with respect to the reverse Sauer inequality if |st(ℱ)|=|ℱ|. The authors in [7] proved that a set system is extremal with respect to the original Sauer inequality exactly when it is extremal with respect to the reverse one, and thus in this case, Sh(ℱ)=st(ℱ).Similar to the case ofSh(ℱ), st(ℱ) can also be obtained from the standard monomials of the vanishing ideal I(ℱ), namely, if viewed as a set of monomials, then it is the collection of those monomials which are standard monomials for all lexicographic term orders.For a set systemℱ⊆2[n] and a set B⊆[n], denote the set family {I⊆[n]∖B|I+2B⊆ℱ} by ℱ(B). We remark that if B={i1,…,im}⊆[n], then ℱ(B) is just Mi1(Mi2(⋯Mim(ℱ)⋯)) and, hence, is s-extremal if ℱ is such. This together with the fact that s-extremality of a set system implies the connectedness of its inclusion graph proves in a simple way the “if” direction of the following remarkable result of Bollobás and Radcliffe [7, Theorem  3].Theorem 11 (see [7]).
ℱ
⊆
2
[
n
] is s-extremal iff Gℱ(B) is connected for every B⊆[n].Now, we prepare the ground for the proof of Theorem9 and return to the algebraic point of view. Let ℱ⊆2[n] be an arbitrary family, and fix one term order ≺ on the monomials in 𝔽[x1,…,xn]. Suppose that we have at our disposal a Gröbner basis 𝔾 of I(ℱ) with respect to a term order ≺ (e.g., in the s-extremal case, we can compute one as described in Section 4). From 𝔾, we can compute a Gröbner basis for I(ℱ|X); we only have to take the polynomials in 𝔾 depending only on the variables xi,i∈X. In general, for a finite set of polynomials 𝔾⊆𝔽[x1,…,xn], denote 𝔾∩𝔽[xi|i∈X] by 𝔾|X. The leading term lt(f) of a nonzero polynomial f∈𝔽[x1,…,xn] with respect to ≺ is lm(f) together with its coefficient from 𝔽. The S-polynomial of nonzero polynomials f,g in 𝔽[x1,…,xn] is
(23)S(f,g)=Llt(f)f-Llt(g)g,
where L is the least common multiple of lm(f) and lm(g). Buchberger’s theorem [19, Theorem 1.7.4] states that a finite set 𝔾 of polynomials in 𝔽[x1,…,xn] is a Gröbner basis for the ideal generated by 𝔾 iff the S-polynomial of any two polynomials from 𝔾 can be reduced to 0 using 𝔾. (For more details on reduction and proofs, see [19, Chapter 1].)Proof of Theorem9.
The facts thatℱ⊆𝒢 and VC-dim(𝒢)=t just follow immediately from the definition of 𝒢.
Now, fix one term order≺ and one 2t+1 element subset X of [n]. Since by assumption ℱ|X is extremal, according to Proposition 8, the polynomials of the form fS,H, where S is a minimal element outside Sh(ℱ|X) and H is the unique subset of S such that H∉(ℱ|X)|S, together with {xi2-xi|i∈X} form a Gröbner basis 𝔾X of I(ℱ|X) with respect to ≺. We have
(24)VC-dim(ℱ|X)≤VC-dim(ℱ)=t;
hence, |S|≤t+1 for all polynomials of the form fS,H in 𝔾X. Write
(25)𝔾:=⋃X⊆[n],|X|=2t+1‍𝔾X.
Note that a polynomialfS,H from 𝔾 is a member of 𝔾X for all 2t+1 element subsets X for which S⊆X. First, we prove using Buchberger’s theorem that 𝔾 is a Gröbner basis of 〈𝔾〉 with respect to ≺. Take two polynomials f,g∈𝔾, and let m be the number of variables occurring in them. If m≤2t+1, then there is some 2t+1 element set X such that f,g∈𝔾X. However, since 𝔾X is a Gröbner basis of I(ℱ|X), S(f,g) can be reduced to 0 using 𝔾X and so using 𝔾 with respect to ≺ as well. On the other hand, m>2t+1 is possible only if f=fS,H and g=fS′,H′ for some appropriate sets H⊆S,H′⊆S′ such that S∩S′=∅ and |S|=|S′|=t+1. The leading terms of fS,H and fS′,H′ are ∏i∈S‍xi and ∏j∈S′‍xj, respectively; so, we can write them in the following forms:
(26)f=fS,H=∏i∈S‍xi︸xS+f′,g=fS′,H′=∏j∈S′‍xj︸xS′+g′,
where f′ and g′ depend on disjoint sets of variables. Consider
(27)S(f,g)=S(fS,H,fS′,H′)=xS′f′-xSg′.
Here, if we replacexS′ by -g′ and xS by -f′, the resulting polynomial will be identically 0; that is, reducing S(f,g) using f,g∈𝔾 gives 0. Moreover, the previous reasoning works for all term orders ≺; so, 𝔾 is a Gröbner basis of 〈𝔾〉 for all term orders. Consider next
(28)A:=𝔽[x1,…,xn]/〈xi2-xi,i∈[n]〉.
Clearly, we have{xi2-xi|i∈[n]}⊆𝔾, and so 〈𝔾〉 defines also an ideal of A. A is actually isomorphic to the ring of all functions from {0,1}n to 𝔽, which in turn is isomorphic to 𝔽2n. In this ring, every ideal is the intersection of maximal ideals, and, hence, every ideal is a radical ideal. This implies that every ideal in A, in particular 〈𝔾〉 as well, is a vanishing ideal of some finite point set from {0,1}n. When considering the 0-1 vectors as characteristic vectors, this finite point set also defines a finite set system. It is not difficult to see that in case of 〈𝔾〉, the only possible candidate for this set system is 𝒢 itself; so, 〈𝔾〉=I(𝒢). However, in this case, we get that 𝔾 is a Gröbner basis of I(𝒢) for all term orders, and, hence, according to Proposition 8,𝒢 is s-extremal.
Finally, we note that ifℱ itself is already s-extremal, then according to Proposition 8,𝔾 is a Gröbner basis for I(ℱ) as well, and so ℱ=𝒢.


## 6. Concluding Remarks

Concerning the structure of s-extremal set systems, the question arises whether an extremal family can be built up from the empty system by adding sets to it one-by-one in such a way that at each step we have an s-extremal family.Open Problem 1. For a nonempty s-extremal family ℱ⊆2[n], does there always exist a set F∈ℱ such that ℱ∖{F} is still s-extremal?From [7, Theorem 2], we know that ℱ is s-extremal iff 2[n]∖ℱ is s-extremal; thus, the previous question has an equivalent form.Open Problem 2. For an s-extremal family ℱ⊊2[n], does there always exist a set F∉ℱ such that ℱ∪{F} is still s-extremal?There are several special cases when the answer appears to be true.(1) Ifℱ is a nonempty downset (F∈ℱ, and H⊆F; then, H∈ℱ), then ℱ is extremal since Sh(ℱ)=ℱ. Moreover, in this case if, we omit a maximal element from ℱ; then, it remains still a downset, and so it will be still s-extremal.(2) Ifℱ is an extremal family of VC-dimension 1, then according to Proposition 2, if we omit a set corresponding to a leaf, that is, to a vertex of degree 1 in Gℱ, then the resulting set system will still be extremal.(3) Anstee in [20] constructed set systems ℱ⊆2[n], |ℱ|=(n0)+(n1)+(n2) without triangles, that is, set systems with the property that for all 3-element subsets F, we have that ℱ|F does not contain all 2-element subsets of F. Note that, in particular, VC-dim(ℱ) is bounded from above by 2; hence, we have that Sh(ℱ)⊆([n]0)∪([n]1)∪([n]2), implying that |Sh(ℱ)|≤(n0)+(n1)+(n2). Comparing the sizes of ℱ and Sh(ℱ), we obtain that such set systems are s-extremal.Clearly, any such set systemℱ contains the extremal subsystem ([n]0)∪([n]1). For the remaining part of these set systems, Anstee’s construction can be interpreted in an inductive way as follows. (i)
Letℱ1:=([n]0)∪([n]1).(ii)
Fork=2,3,…,n, suppose that we already constructed ℱk-1. Let 𝒢k-1 be the collection of all k-1-element sets in ℱk-1. Define Gk-1 to be a graph, whose vertex set is 𝒢k-1, and there is an edge between A,B∈𝒢k-1 exactly when |A∆B|=2. Take a spanning tree Tk-1 of Gk-1. Consider
(29)ℱk:=ℱk-1∪{A∪B∣(A,B)isanedgeofTk-1}.(iii)
Letℱ:=ℱn.It is not hard to prove that when we addA∪B, there will be a unique new element that gets into the family of shattered sets, namely, A∆B; hence, the resulting system after each step will be s-extremal. Reversing it, if ℱ is such an example, then its elements can be deleted one-by-one in such a way that the remaining set system is s-extremal after each step.(4) More generally, one can consider set systemsℱ⊆2[n] with the property that for all t-element subsets F, we have that ℱ|F does not contain all l-element subsets of F, for some l with n≥t≥l≥0. Furedi and Quinn in [9] constructed for all values n≥t≥l≥0 a set system ℱ(n,t,l) with the desired property and of size |ℱ(n,t,l)|=∑i=0t-1‍(ni). The same argument as aforementioned shows that Sh(ℱ(n,t,l)) consists of all sets of size at most t-1, and, hence, ℱ(n,t,l) is s-extremal for all possible values. Their construction is as follows.Forx1,…,xi∈[n], x1<⋯<xi, let
(30)E(x1,…,xi)={x∈[n]∣x=xjforj≤l}∪{x∈[n]∣x>xlbutx≠xjforanyj>l};
in particular, E(∅)=∅. Let ℱ(n,t,l) consist of all E(x1,…,xi), where i≤t-1. Order the sets of ℱ(n,t,l) as follows: E(X)≻E(Y) if either |X|>|Y| or |X|=|Y|, and X≻Y with respect to the standard lexicographic ordering. It is not hard to see that if we remove the elements of ℱ(n,t,l) with respect to this ordering one-by-one, starting from the largest one, then each time when we remove some E(X), X is eliminated from the family of shattered sets; hence, after each step, the resulting family will be still s-extremal.



---

*Source: 126214-2013-02-27.xml*