## Density and dimension. (Densité et dimension.)(French. English summary)Zbl 0504.60006

Summary: A class $${\mathcal S}$$ of subsets of a set $$X$$ is called a Vapnik-Chervonenkis class if the growth of the function $$\Delta ^{\mathcal S}: r\to \mathrm{Sup} \{| A\cap|| A\subset X,\,| A| = r\}$$ is polynomial; these classes have proved to be useful in Statistics and Probability (see for example, V. N. Vapnik and A. Ya. Chervonenkis, Theor. Probab. Appl. 16, 264–280 (1971); translation from Teor. Veroyatn. Primen. 16, 264–279 (1971; Zbl 0247.60005)] and R. M. Dudley [Ann. Probab. 6, 899–929 (1978; Zbl 0404.60016)]).
The present paper is a survey on Vapnik-Chervonenkis classes. Moreover we prove here many new results, among them the following:
– a subset $${\mathcal S}$$ of $$2^X$$ is a Vapnik-Chervonenkis class if and only if the number of atoms of the $$\sigma$$-algebra generated by any collection of $$r$$ members of $${\mathcal S}$$ if no more than $$Cr^s$$ (where $$C$$ and $$s$$ are two positive real numbers);
– if $${\mathcal S}$$ is a subset of $$2^X$$, every probability law $$P$$ on the $$\sigma$$-algebra generated by $${\mathcal S}$$ defines a semimetric $$d_p: S,S'\longrightarrow P(S\Delta S')$$ on the class $${\mathcal S}$$, and the entropy dimension of the space $$({\mathcal S},d_p)$$ will be denoted $$\overline{\dim}({\mathcal S},d_p)$$ ; the class $${\mathcal S}$$ is a Vapnik-Chervonenkis class if and only if $$\text{Sup}_P\,\overline{\dim} ({\mathcal S},d_p)$$ is finite.
The present paper contains other new results, some of them being stated without proof in my note [C. R. Acad. Sci., Paris, Sér. I 292, 921–924 (1981; Zbl 0466.04002)].
Show Scanned Page ### MSC:

 05A20 Combinatorial inequalities 52A37 Other problems of combinatorial convexity 03E05 Other combinatorial set theory

### Keywords:

Vapnik-Chervonenkis class

### Citations:

Zbl 0247.60005; Zbl 0404.60016; Zbl 0466.04002
Full Text: