×

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)].

MSC:

05A20 Combinatorial inequalities
52A37 Other problems of combinatorial convexity
03E05 Other combinatorial set theory
PDF BibTeX XML Cite
Full Text: DOI Numdam EuDML

References:

[1] R. ALEXANDER, Planes for which the lines are the shortest path, Illinois J. of Math., 22 (1978), 177-190. · Zbl 0379.50002
[2] R. ALEXANDER, Metrics on rn which possess a crofton formula, Notices AMS, 26 (1979), A-278.
[3] R.V. AMBARTZUMIAN, A note on pseudometrics on the plane, Z. Warscheinlich keitstheorie, 37 (1976), 145-155. · Zbl 0325.28020
[4] P. ASSOUAD, Espaces métriques, plongements, facteurs, Thèse, Université de Paris-Sud, (1977). · Zbl 0396.46035
[5] P. ASSOUAD, Pseudodistances, facteurs et dimension métrique, Séminaire d’Analyse Harmonique 1979/1980 (Orsay) Publications Mathématiques d’Orsay n° 81-07, pp. 1-33. · Zbl 0486.54021
[6] P. ASSOUAD, Sur LES classes de vapnik-cervonenkis, C. R. A. S., Paris, 292 (1981), 921-924. · Zbl 0466.04002
[7] E.G. BAJMOCZY, I. BARANY : On a common generalization of Borsuk’s and Radon’s theorems, Acta Math. Acad. Scient. Hungar., 34 (1979), 347-350. · Zbl 0446.52010
[8] R.G. BLAND, M. LAS VERGNAS, Orientability of matroïds, J. of Comb. Th., B. 24 (1978), 94-123. · Zbl 0374.05016
[9] K. BORSUK, W. SZMIELEW, Foundations of geometry (english transl.), North Holland (1960). · Zbl 0093.33301
[10] H. BUSEMANN, Desarguesian spaces, Proc. of Symp. in Pure Math., 28 (1976), 131-141. · Zbl 0352.50010
[11] P. CARTIER. Arrangements d’hyperplans : un chapitre de géométrie combinatoire, Seminaire Bourbaki (1980), exposé n° 651. · Zbl 0483.51011
[12] L. DANZER, B. GRUNBAUM, V. KLEE, Helly’s theorem and its relatives, Proc. of Symp. in Pure Math., 7 (1963), 101-180. · Zbl 0132.17401
[13] P. DEMBOWSKI, Finite geometries, Springer, 1968. · Zbl 0159.50001
[14] R.M. DUDLEY, Central limit theorems for empirical measures, Ann. of Prob., 6 (1978), 899-929. · Zbl 0404.60016
[15] R.M. DUDLEY, Balls in rk do not cut all subsets of (k + 2) points, Advances Math., 31 (1979), 306-308. · Zbl 0408.05001
[16] R.M. DUDLEY, Vapnik-cervonenkis donsker classes of functions, preprint (1980). · Zbl 0511.60046
[17] M. DURST, R.M. DUDLEY, Empirical processes, Vapnik Cervonenkis classes and Poisson processes, Probability and Math. Stat., 1 (1981) to appear. · Zbl 0502.60019
[18] J. ECKHOFF, Radon’s theorem revisited, In Contributions to geometry, Proc. of the Geometry Symp. in Siegen 1978, Birkhaüser (1979) 164-185. · Zbl 0445.52009
[19] G. FICHTENHOLZ, K. KANTOROVITCH, Sur LES opérations linéaires dans l’espace des fonctions bornées, Studia Math., 5 (1934), 69-98. · JFM 60.1074.05
[20] J.E. GOODMAN, R. POLLACK, Proof of grünbaum’s conjecture on the stretchability of certain arrangements of pseudolines, J. Comb. Th, A 29 (1980), 385-390. · Zbl 0457.51006
[21] B. GRUNBAUM, Arrangements and spreads, CBMS Regional Conference Series in Math., n° 10 (1972). · Zbl 0249.50011
[22] B. HAJEK, Stochastic integration, Markov property and measure transformation of random fields, Ph. D. Dissertation, Berkeley (1979).
[23] R.E. JAMISON, A general theory of convexity, Doct. Dissert., Univ. of Washington (Seattle, 1974).
[24] T. KOVARI, V.T. SOS, P. TURAN, On a problem of K. zarankiewicz, Colloquium Math., 3 (1954), 50-57. · Zbl 0055.00704
[25] G.G. LORENTZ, Lower bound for the degree of approximation, Trans. Amer, Math. Soc., 97 (1960), 25-34. · Zbl 0128.06701
[26] B. REZNICK, Banach spaces with polynomial norms, Pac. J. Math., 82 (1979), 223-235. · Zbl 0413.46013
[27] G. RINGEL, Teilungen der ebene durch geraden oder topologische geraden, Math. Z., 64 (1955), 79-102. · Zbl 0070.16108
[28] C.A. ROGERS, Hausdorff measures, Cambridge University Press (1970). · Zbl 0204.37601
[29] H.P. ROSENTHAL, A characterization of Banach spaces containing l1, Proc. Nat. Acad. Sci. USA, 71 (1974), 2411-2413. · Zbl 0297.46013
[30] N. SAUER, On the density of families of sets, J. Comb. Th., A 13 (1972) 145-147. · Zbl 0248.05005
[31] I.J. SCHOENBERG, Metric spaces and positive definite functions, Transact. Amer. Math. Soc., 44 (1938), 522-536. · JFM 64.0617.02
[32] H.S. SHAPIRO, Some negative theorems of approximation theory, Michigan Math. J., 11 (1964), 211-217. · Zbl 0123.09202
[33] S. SHELAH, A combinatorial problem ; stability and order for models and theories in infinitary languages, Pacific J. Math., 41 (1972) 247-261. · Zbl 0239.02024
[34] G. SIERKSMA, Generalized Radon partitions in convexity spaces, preprint (1980). · Zbl 0489.52001
[35] E.H. SPANIER, Algebric topology, Mc Graw Hill (1966).
[36] H.M. STARK, An introduction to number theory, Markham Publ. Co., 1971.
[37] E. SZPILRAJN (Marczewski), Ensembles indépendants et mesures non séparables, C.R.A.S., Paris, 207 (1938), 768-770. · JFM 64.0192.03
[38] H. TVERBERG, A generalization of Radon’s theorem, J. of the London Math. Soc., 41 (1966), 123-128. · Zbl 0131.20002
[39] V.N. VAPNIK, A. YA. CERVONENKIS, On the uniform convergence of relative frequencies of events to their probabilities, Theor. Prob. Appl., 16 (1971), 264-280. · Zbl 0247.60005
[40] H.E. WARREN, Partitions by real algebraic varieties and applications to questions of nonlinear approximation, Bull. AMS, 73 (1967) 192-194. · Zbl 0223.14027
[41] H.E. WARREN, Lower bounds for approximation by nonlinear manifolds, Trans. AMS, 133 (1968), 167-178. · Zbl 0174.35403
[42] D.J.A. WELSH, Matroïd theory, Academic Press (1976). · Zbl 0343.05002
[43] R.S. WENOCUR, R.M. DUDLEY, Some special vapnik-cervonenkis classes, Discrete Math., 33 (1981), 313-318. · Zbl 0459.60008
[44] B.J. BIRCH : On 3N points in a plane, Proc. Cambridge Phil. Soc., 55 (1959), 289-293. · Zbl 0089.38502
[45] J.A. BONDY : Induced subsets, J. Comb. Th., B 12 (1972), 201-202. · Zbl 0211.56901
[46] K. GLAZEK : Some old and new problems in the independence theory, Colloquium Math., 42 (1979), 127-189. · Zbl 0432.08001
[47] M.G. KARPOVSKY, V.D. MILMAN : Coordinate density of sets of vectors, Discrete Math., 24 (1978), 177-184. · Zbl 0401.05015
[48] P. TOMASTA : “dart calculus” of induced subsets, Discrete Math., 34 (1981), 195-198. · Zbl 0475.05002
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.