Vapnik-Chervonenkis density on indiscernible sequences, stability, and the maximum property. (English) Zbl 1372.03064

Summary: This paper presents some finite combinatorics of set systems with applications to model theory, particularly the study of dependent theories. There are two main results. First, we give a way of producing lower bounds on \(\mathrm{VC}_{\mathrm{ind}}\)-density and use it to compute the exact \(\mathrm{VC}_{\mathrm{ind}}\)-density of polynomial inequalities and a variety of geometric set families. The main technical tool used is the notion of a maximum set system, which we juxtapose to indiscernibles. In the second part of the paper we give a maximum set system analogue to Shelah’s characterization of stability using indiscernible sequences.


03C45 Classification theory, stability, and related concepts in model theory
05D05 Extremal set theory
Full Text: DOI arXiv Euclid


[1] Aschenbrenner, M., A. Dolich, D. Haskell, H. D. Macpherson, and S. Starchenko, “Vapnik-Chervonenkis density in some theories without the independence property, II,” Notre Dame Journal of Formal Logic , vol. 54 (2013), pp. 311-63. · Zbl 1436.03185
[2] Ben-David, S., and A. Litman, “Combinatorial variability of Vapnik-Chervonenkis classes with applications to sample compression schemes,” Discrete Applied Mathematics , vol. 86 (1998), pp. 3-25. · Zbl 0905.68048
[3] Dudley, R. M., Uniform Central Limit Theorems , vol. 63 of Cambridge Studies in Advanced Mathematics , Cambridge University Press, Cambridge, 1999. · Zbl 0951.60033
[4] Floyd, S., “Space-bounded learning and the Vapnik-Chervonenkis dimension,” pp. 349-64 in Proceedings of the Second Annual Workshop on Computational Learning Theory (Santa Cruz, Calif., 1989) , Morgan Kaufmann, San Mateo, Calif., 1989. · Zbl 0747.68041
[5] Guingona, V., and C. D. Hill, “On VC-density over indiscernible sequences,” preprint, [math.LO]. arXiv:1108.2554v4 · Zbl 1334.03034
[6] Hodges, W., A Shorter Model Theory , Cambridge University Press, Cambridge, 1997. · Zbl 0316.02047
[7] Kaplan, I., A. Onshuus, and A. Usvyatsov, “Additivity of the dp-rank,” Transactions of the American Mathematical Society , vol. 365 (2013), pp. 5783-804. · Zbl 1323.03041
[8] Johnson, H. R., “Dp-rank and forbidden configurations,” Notre Dame Journal of Formal Logic , vol. 54 (2013), pp. 1-15. · Zbl 1276.03035
[9] Johnson, H. R., and M. C. Laskowski, “Compression schemes, stable definable families, and o-minimal structures,” Discrete and Computational Geometry , vol. 43 (2010), pp. 914-26. · Zbl 0647.03024
[10] Kuzmin, D., and M. K. Warmuth, “Unlabeled compression schemes for maximum classes,” Journal of Machine Learning Research , vol. 8 (2007), pp. 2047-81. · Zbl 1222.68239
[11] Laskowski, M. C., “Vapnik-Chervonenkis classes of definable sets,” Journal of the London Mathematical Society (2) , vol. 45 (1992), pp. 377-84. · Zbl 0766.60016
[12] Rubinstein, B. I. P., and J. H. Rubinstein, “A geometric approach to sample compression,” Journal of Machine Learning Research , vol. 13 (2012), pp. 1221-61. · Zbl 1283.68301
[13] Sauer, N., “On the density of families of sets,” Journal of Combinatorial Theory Series A , vol. 13 (1972), pp. 145-47. · Zbl 0248.05005
[14] Shelah, S., “A combinatorial problem: Stability and order for models and theories in infinitary languages,” Pacific Journal of Mathematics , vol. 41 (1972), pp. 247-61. · Zbl 0239.02024
[15] S. Shelah Classification Theory and the Number of Nonisomorphic Models , 2nd edition, vol. 92 of Studies in Logic and the Foundations of Mathematics , North-Holland, Amsterdam, 1990.
[16] Vapnik, V., and A. Chervonenkis, “On the uniform convergence of relative frequencies of events to their probabilities,” Theory of Probability and its Applications , vol. 16 (1971), pp. 264-80. · Zbl 0247.60005
[17] Welzl, E., “Complete range spaces,” unpublished notes, 1987.
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.