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

Johnson, Hunter

Notre Dame J. Formal Logic 56, No. 4, 583-593 (2015).

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.

MSC:

03C45	Classification theory, stability, and related concepts in model theory
05D05	Extremal set theory

Keywords:

VC-density; VC-dimension; NIP; stability

References:

[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.