We show that the family of all lines in the plane which is a VC class of index 2 cannot be obtained in a finite number of steps starting with VC classes of index 1 and applying the operations of intersection and union. This confirms a common belief among specialists and solves a question asked by several authors.
@article{bwmeta1.element.bwnjournal-article-cmv74i1p93bwm,
author = {Agata Smoktunowicz},
title = {A remark on Vapnik-Chervonienkis classes},
journal = {Colloquium Mathematicae},
volume = {72},
year = {1997},
pages = {93-98},
zbl = {0892.60014},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-cmv74i1p93bwm}
}
Smoktunowicz, Agata. A remark on Vapnik-Chervonienkis classes. Colloquium Mathematicae, Tome 72 (1997) pp. 93-98. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-cmv74i1p93bwm/
[000] [1] R. M. Dudley, Uniform Central Limit Theorems, Cambridge University Press, to appear. | Zbl 0951.60033
[001] [2] P. Erdős and G. Szekeres, A combinatorial problem in geometry, Compositio Math. 2 (1939), 463-470. | Zbl 0012.27010
[002] [3] J. Hoffmann-Jοrgensen, K.-L. Su and R. L. Taylor, The law of large numbers and the Ito-Nisio theorem for vector valued random fields, J. Theoret. Probab. 10 (1997), 145-183. | Zbl 0870.60006
[003] [4] S. Kwapień, On maximal inequalities for sums of independent random variables, in: XIII Jubileuszowy Zjazd Matematyków Polskich, Referaty, Wydawnictwa PTM, 1994 (in Polish).
[004] [5] M. Ledoux and M. Talagrand, Probability in Banach Spaces, Springer, 1991.