%0 Journal Article
%T Shattering-Extremal Set Systems of Small VC-Dimension
%A Tam¨˘s M¨¦sz¨˘ros
%A Lajos R¨®nyai
%J ISRN Combinatorics
%D 2013
%R 10.1155/2013/126214
%X We say that a set system shatters a given set if . 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. 1. Introduction Throughout this paper, will be a positive integer, and the set will be referred to shortly as , the power set of it as , and the family of subsets of size as ( ). The central notion of our study is shattering. We say that a set system shatters a given set if . The family of subsets of shattered by is denoted by . The following inequality gives a bound on the size of . Proposition 1. . 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¨C9]. The Vapnik-Chervonenkis dimension of a set system , denoted by , 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 -dimension of is bounded by some fixed natural number . After the Introduction, in Section 2, we first investigate s-extremal set systems of -dimension 1 from a graph theoretical point of view. We give a bijection between the family of such set systems on the ground set and trees on 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
%U http://www.hindawi.com/journals/isrn.combinatorics/2013/126214/