zbMATH — the first resource for mathematics

The VC-dimension of Sperner systems. (English) Zbl 0929.05081
A set system \(\mathcal F\) on the finite underlying set \(X\) shatters a set \(D \subset X\) if the trace of \(\mathcal F\) on \(D\) is the power-set of \(D.\) The maximum size of a set shattered by \(\mathcal F\) is the VC-dimension of the family \(\mathcal F\). P. Frankl started to investigate maximum Sperner families having bounded VC-dimension. This paper evaluates the maximum possible VC-dimension of a Sperner family and gives an upper bound for the size of a Sperner family with this maximum VC-dimension.

05D05 Extremal set theory
Full Text: DOI
[1] Ahlswede, R.; Khachatrian, L.H., Counterexample to the frankl – pack conjecture for uniform, dense families, Combinatorica, 17, 299-301, (1997) · Zbl 0886.05109
[2] Anstee, R.P.; Sali, A., Sperner sets of bounded VC-dimension, Discrete math., 175, 13-21, (1997) · Zbl 0887.05052
[3] Bollobás, Combinatorics, (1986), Cambridge Univ. Press Cambridge
[4] Frankl, P., On the trace of finite sets, J. combin. theory ser. A, 34, 41-45, (1983) · Zbl 0505.05001
[5] Frankl, P., Traces of antichains, Graphs combin., 5, 295-299, (1989) · Zbl 0759.05093
[6] Frankl, P.; Pack, J., On disjointly representable sets, Combinatorica, 4, 39-45, (1984) · Zbl 0534.05003
[7] M. Perles, umpublished manuscript.
[8] Sauer, N., On the density of families of sets, J. combin. theory ser. A, 13, 145-147, (1972) · Zbl 0248.05005
[9] Shelah, S., A combinatorial problem; stability and order for models in infinitary languages, Pacific J. math., 41, 271-276, (1972)
[10] Vapnik, V.N.; Chervonenkis, A.Ya., On the uniform convergence of relatives frequencies of events to their probability, Theory probab. appl., 16, 264-280, (1971) · Zbl 0247.60005
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.