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–9]. 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
References
[1]
R. Aharoni and R. Holzman, Personal communication.
[2]
A. Pajor, Sous-Spaces 1: Des Espaces de Banach Travaux en Cours, Hermann, Paris, France, 1985.
[3]
N. Sauer, “On the density of families of sets,” Journal of Combinatorial Theory A, vol. 13, no. 1, pp. 145–147, 1972.
[4]
S. Shelah, “A combinatorial problem: stability and order for models and theories in infinitary language,” Pacific Journal of Mathematics, vol. 41, pp. 247–261, 1972.
[5]
R. P. Anstee, L. Rónyai, and A. Sali, “Shattering news,” Graphs and Combinatorics, vol. 18, no. 1, pp. 59–73, 2002.
[6]
B. Bollobas, I. Leader, and A. J. Radcliffe, “Reverse kleitman inequalities,” Proceedings of the London Mathematical Society, vol. s3-58, pp. 153–168, 1989.
[7]
B. Bollobás and A. J. Radcliffe, “Defect Sauer results,” Journal of Combinatorial Theory A, vol. 72, no. 2, pp. 189–208, 1995.
[8]
P. Frankl, S-Extremal Set Systems, Handbook of Combinatorics, vol. 2, MIT Press, Cambridge, Mass, USA, 1996.
[9]
Z. Furedi and F. Quinn, “Traces of finite sets,” Ars Combinatoria, vol. 18, pp. 195–200, 1983.
[10]
G. Greco, “Embeddings and the trace of finite sets,” Information Processing Letters, vol. 67, no. 4, pp. 199–203, 1998.
[11]
R. Diestel, Garph Theory, Springer, New York, NY, USA, 2000, Electronic Edition 2000.
[12]
O. Pikhurko, “Generating edge-labeled trees,” American Mathematical Monthly, vol. 112, no. 10, pp. 919–921, 2005.
[13]
L. Ronyai and T. Meszaros:, “Some combinatorial applications of grobner bases,” in Proceedings of the 4th International Conference on Algebraic Informatics (CAI '11), vol. 6742 of Lecture Notes in Computer Science, 2011.
[14]
B. Buchberger, “An algorithm for finding the basis elements in the residue class ring modulo a zero dimensional polynomial ideal,” Journal of Symbolic Computation, vol. 41, pp. 475–511, 2006, Special Issue on Logic, Mathematics, and Computer Science: Interactions; Ein Algorithmus zum Auffnden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal. Doctoral thesis, University of Innsbruck, 1965.
[15]
B. Buchberger, “Ein algorithmisches Kriterium für die L？sbarkeit eines algebraischen Gleichungssystems,” Aequationes Mathematicae, vol. 4, no. 3, pp. 374–383, 1970.
[16]
B. Buchberger, “An algorithmic criterion for the solvability of algebraic systems of equations,” B. Buchberger and F. Winkler, Eds., vol. 251 of London Mathematical Society Lecture Note Seriesm, pp. 535–545, Gr？bner Bases and Applications; Cambridge University Press, 1998.
[17]
B. Buchberger, “Grobner-bases: an algorithmic method in polynomial ideal theory,” in Multidimensional Systems Theory—Progress, Directions and Open Problems in Multidimensional Systems Theory, N. K. Bose, Ed., pp. 184–232, Reidel Publishing Company, Boston, Mass, USA, 1985.
[18]
D. Cox, J. Little, and D. O'Shea, Ideals, Varieties, and Algorithms, Springer, Berlin, Germany, 1992.
[19]
W. W. Adams and P. Loustaunau, An Introduction to Grobner Bases, Graduate Studies in Mathematics, vol. 3, American Mathematical Society, 1994.
[20]
R. P. Anstee, “Properties of (0-1) matrices with no triangles,” Journal of Combinatiral Theory A, vol. 29, pp. 186–198, 1980.
