$\mathrm {VC}_{\ell }$-dimension and the jump to the fastest speed of a hereditary $\mathcal {L}$-property
HTML articles powered by AMS MathViewer
- by C. Terry PDF
- Proc. Amer. Math. Soc. 146 (2018), 3111-3126 Request permission
Abstract:
In this paper we investigate a connection between the growth rates of certain classes of finite structures and a generalization of $\mathrm {VC}$-dimension called $\mathrm {VC}_{\ell }$-dimension. Let $\mathcal {L}$ be a finite relational language with maximum arity $r$. A hereditary $\mathcal {L}$-property is a class of finite $\mathcal {L}$-structures closed under isomorphism and substructures. The speed of a hereditary $\mathcal {L}$-property $\mathcal {H}$ is the function which sends $n$ to $|\mathcal {H}_n|$, where $\mathcal {H}_n$ is the set of elements of $\mathcal {H}$ with universe $\{1,\ldots , n\}$. It was previously known that there exists a gap between the fastest possible speed of a hereditary $\mathcal {L}$-property and all lower speeds, namely between the speeds $2^{\Theta (n^r)}$ and $2^{o(n^r)}$. We strengthen this gap by showing that for any hereditary $\mathcal {L}$-property $\mathcal {H}$, either $|\mathcal {H}_n|=2^{\Theta (n^r)}$ or there is $\epsilon >0$ such that for all large enough $n$, $|\mathcal {H}_n|\leq 2^{n^{r-\epsilon }}$. This improves what was previously known about this gap when $r\geq 3$. Further, we show this gap can be characterized in terms of $\mathrm {VC}_{\ell }$-dimension, therefore drawing a connection between this finite counting problem and the model theoretic dividing line known as $\ell$-dependence.References
- V. E. Alekseev, Hereditary classes and coding of graphs, Problemy Kibernet. 39 (1982), 151–164 (Russian). MR 694829
- Noga Alon, József Balogh, Béla Bollobás, and Robert Morris, The structure of almost all graphs in a hereditary property, J. Combin. Theory Ser. B 101 (2011), no. 2, 85–110. MR 2763071, DOI 10.1016/j.jctb.2010.10.001
- Ashwini Aroskar and James Cummings, Limits, regularity and removal for finite structures, arXiv:1412.808v1 [math.LO], 2014.
- József Balogh, Béla Bollobás, and David Weinreich, The speed of hereditary properties of graphs, J. Combin. Theory Ser. B 79 (2000), no. 2, 131–156. MR 1769217, DOI 10.1006/jctb.2000.1952
- József Balogh, Béla Bollobás, and David Weinreich, The penultimate rate of growth for graph properties, European J. Combin. 22 (2001), no. 3, 277–289. MR 1822715, DOI 10.1006/eujc.2000.0476
- József Balogh, Béla Bollobás, and David Weinreich, A jump to the Bell number for hereditary graph properties, J. Combin. Theory Ser. B 95 (2005), no. 1, 29–48. MR 2154176, DOI 10.1016/j.jctb.2005.02.004
- Özlem Beyarslan, Random hypergraphs in pseudofinite fields, J. Inst. Math. Jussieu 9 (2010), no. 1, 29–47. MR 2576797, DOI 10.1017/S1474748009000073
- Béla Bollobás and Andrew Thomason, Projections of bodies and hereditary properties of hypergraphs, Bull. London Math. Soc. 27 (1995), no. 5, 417–424. MR 1338683, DOI 10.1112/blms/27.5.417
- Béla Bollobás and Andrew Thomason, Hereditary and monotone properties of graphs, The mathematics of Paul Erdős, II, Algorithms Combin., vol. 14, Springer, Berlin, 1997, pp. 70–78. MR 1425205, DOI 10.1007/978-3-642-60406-5_{7}
- R. C. Bose, On the construction of balanced incomplete block designs, Ann. Eugenics 9 (1939), 353–399. MR 1221, DOI 10.1111/j.1469-1809.1939.tb02219.x
- Peter J. Cameron, The age of a relational structure, Discrete Math. 95 (1991), no. 1-3, 49–67. Directions in infinite graph theory and combinatorics (Cambridge, 1989). MR 1141931, DOI 10.1016/0012-365X(91)90329-Z
- Artem Chernikov, Daniel Palacin, and Kota Takeuchi, On n-dependence, arXiv:1411.0120 [math.LO], 2014.
- Nadja Hempel, On $n$-dependent groups and fields, MLQ Math. Log. Q. 62 (2016), no. 3, 215–224. MR 3509704, DOI 10.1002/malq.201400080
- Djamila Oudrar, Sur lénumération de structure discrètes, une approche par la théorie des relations, arXiv:1604.05839 [math.CO], 2016.
- Maurice Pouzet and Nicolas M. Thiéry, Some relational structures with polynomial growth and their associated algebras I: Quasi-polynomiality of the profile, Electron. J. Combin. 20 (2013), no. 2, Paper 1, 35. MR 3066340
- S. Shelah, Classification theory and the number of nonisomorphic models, 2nd ed., Studies in Logic and the Foundations of Mathematics, vol. 92, North-Holland Publishing Co., Amsterdam, 1990. MR 1083551
- Saharon Shelah, Definable groups for dependent and 2-dependent theories, Sarajevo J. Math. 13(25) (2017), no. 1, 3–25. MR 3666349, DOI 10.5644/sjm
- Saharon Shelah, Dependent dreams: recounting types, arXiv:1202.5795 [math.LO], 2012.
- Saharon Shelah, Strongly dependent theories, Israel J. Math. 204 (2014), no. 1, 1–83. MR 3273451, DOI 10.1007/s11856-014-1111-2
- Pierre Simon, A guide to NIP theories, Lecture Notes in Logic, vol. 44, Association for Symbolic Logic, Chicago, IL; Cambridge Scientific Publishers, Cambridge, 2015. MR 3560428, DOI 10.1017/CBO9781107415133
- Th. Skolem, Some remarks on the triple systems of Steiner, Math. Scand. 6 (1958), 273–280. MR 106852, DOI 10.7146/math.scand.a-10551
- C. Terry, Structure and enumeration theorems for hereditary properties in finite relational languages, arXiv:1607.04902 [math.LO], 2016.
Additional Information
- C. Terry
- Affiliation: Department of Mathematics, University of Maryland, College Park, Maryland 20742-4015
- MR Author ID: 1130819
- Received by editor(s): January 4, 2017
- Received by editor(s) in revised form: September 18, 2017, and October 5, 2017
- Published electronically: February 16, 2018
- Communicated by: Heike Mildenberger
- © Copyright 2018 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 146 (2018), 3111-3126
- MSC (2010): Primary 03C13, 03C45, 05C30, 05C65
- DOI: https://doi.org/10.1090/proc/13976
- MathSciNet review: 3787371