On \(n\)-dependence. (English) Zbl 1529.03198
Summary: In this article, we develop and clarify some of the basic combinatorial properties of the new notion of \(n\)-dependence (for \(1\leq n<\omega\)) recently introduced by S. Shelah [Isr. J. Math. 204, 1–83 (2014; Zbl 1371.03043); Sarajevo J. Math. 13(25), No. 1, 3–25 (2017; Zbl 1424.03016)]. In the same way as dependence of a theory means its inability to encode a bipartite random graph with a definable edge relation, \(n\)-dependence corresponds to the inability to encode a random \((n+1)\)-partite \((n+1)\)-hypergraph with a definable edge relation. We characterize \(n\)-dependence by counting \(\phi\)-types over finite sets (generalizing the Sauer-Shelah lemma, answering a question of Shelah [2014, loc. cit.]), and in terms of the collapse of random ordered \((n+1)\)-hypergraph indiscernibles down to order-indiscernibles (which implies that the failure of \(n\)-dependence is always witnessed by a formula in a single free variable).
MSC:
| 03C45 | Classification theory, stability, and related concepts in model theory |
| 05C55 | Generalized Ramsey theory |
| 05C65 | Hypergraphs |
References:
| [1] | Abramson, F. G., and L. A. Harrington, “Models without indiscernibles,” Journal of Symbolic Logic, vol. 43 (1978), no. 3, pp. 572-600. · Zbl 0391.03027 · doi:10.2307/2273534 |
| [2] | Adler, H., “An introduction to theories without the independence property,” to appear in Archive for Mathematical Logic, preprint, 2008, http://www.logic.univie.ac.at/ adler/docs/nip.pdf. |
| [3] | Aschenbrenner, M., A. Dolich, D. Haskell, D. Macpherson, and S. Starchenko, “Vapnik-Chervonenkis density in some theories without the independence property, I,” Transactions of the American Mathematical Society, vol. 368 (2016), no. 8, pp. 5889-949. · Zbl 1423.03119 · doi:10.1090/tran/6659 |
| [4] | Beyarslan, Ö., “Random hypergraphs in pseudofinite fields,” Journal of the Institute of Mathematics of Jussieu, vol. 9 (2010), no. 1, pp. 29-47. · Zbl 1247.12012 · doi:10.1017/S1474748009000073 |
| [5] | Bohman, T., and P. Keevash, “The early evolution of the \(H\)-free process,” Inventiones Mathematicae, vol. 181 (2010), no. 2, pp. 291-336. · Zbl 1223.05270 · doi:10.1007/s00222-010-0247-x |
| [6] | Bollobás, B., Extremal Graph Theory, Dover Publications, Mineola, New York, 2004. · Zbl 1099.05044 |
| [7] | Cherlin, G. L., and E. Hrushovski, Finite Structures with Few Types, vol. 152 of Annals of Mathematics Studies, Princeton University Press, Princeton, 2003. · Zbl 1024.03001 |
| [8] | Chernikov, A., and P. Simon, “Externally definable sets and dependent pairs II,” Transactions of the American Mathematical Society, vol. 367 (2015), no. 7, pp. 5217-35. · Zbl 1388.03035 · doi:10.1090/S0002-9947-2015-06210-2 |
| [9] | Erdős, P., “On extremal problems of graphs and generalized graphs,” Israel Journal of Mathematics, vol. 2 (1964), pp. 183-90. · Zbl 0129.39905 |
| [10] | Haskell, D., E. Hrushovski, and D. Macpherson, Stable Domination and Independence in Algebraically Closed Valued Fields, vol. 30 of Lecture Notes in Logic, Association for Symbolic Logic, Chicago, 2008. · Zbl 1149.03027 |
| [11] | Hempel, N., “On \(n\)-dependent groups and fields,” Mathematical Logic Quarterly, vol. 62 (2016), no. 3, pp. 215-224. · Zbl 1366.03213 |
| [12] | Hrushovski, E., “On pseudo-finite dimensions,” Notre Dame Journal of Formal Logic, vol. 54 (2013), nos. 3-4, pp. 463-495. · Zbl 1345.03059 · doi:10.1215/00294527-2143952 |
| [13] | Hrushovski, E., and A. Pillay, “On NIP and invariant measures,” J. Eur. Math. Soc. (JEMS), vol. 13 (2011), no. 4, pp. 1005-1061. · Zbl 1220.03016 · doi:10.4171/JEMS/274 |
| [14] | Nešetřil, J., and V. Rödl, “Partitions of finite relational and set systems,” J. Combinatorial Theory Series A, vol. 22 (1977), no. 3, pp. 289-312. · Zbl 0361.05017 |
| [15] | Nešetřil, J., and V. Rödl, “Ramsey classes of set systems,” Journal of Combinational Theory Series A, vol. 34 (1983), no. 2, pp. 183-201. · Zbl 0515.05010 |
| [16] | Ngo, H. Q., “Three proofs of Sauer-Shelah lemma,” lecture notes, http://www.cse.buffalo.edu/ hungngo/classes/2010/711/lectures/sauer.pdf. |
| [17] | Pach, J., and P. K. Agarwal, Combinatorial Geometry, Wiley, New York, 1995. · Zbl 0881.52001 |
| [18] | Scow, L., “Characterization of NIP theories by ordered graph-indiscernibles,” Annals of Pure and Applied Logic, vol. 163 (2012), no. 11, pp. 1624-41. · Zbl 1260.03066 · doi:10.1016/j.apal.2011.12.013 |
| [19] | Scow, L., “Indiscernibles, EM-types, and Ramsey classes of trees,” Notre Dame Journal of Formal Logic, vol. 56 (2015), no. 3, pp. 429-47. · Zbl 1334.03035 · doi:10.1215/00294527-3132797 |
| [20] | Shelah, S., 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. · Zbl 0713.03013 |
| [21] | Shelah, S., “Strongly dependent theories,” Israel Journal of Mathematics, vol. 204 (2014), no. 1, pp. 1-83. · Zbl 1371.03043 · doi:10.1007/s11856-014-1111-2 |
| [22] | Shelah, S., “Definable groups for dependent and 2-dependent theories,” Sarajevo Journal of Mathematics, vol. 13(25) (2017), no. 1, pp. 3-25. · Zbl 1424.03016 |
| [23] | Shelah, S., “Dependent dreams: recounting types,” preprint, arXiv:1202.5795 [math.LO]. |
| [24] | Takeuchi, K., “A characterization of \(n\)-dependent theories,” Lecture Notes: RIMS Kôkyûroku Bessatsu, vol. 1888 (2014), no. 2014.4, pp. 59-66. |
| [25] | Vapnik, V. N., and A. Y. Chervonenkis, “On the uniform convergence of relative frequencies of events to their probabilities,” Theory of Probability and Its Applications, vol. 16 (1971), no. 2, pp. 264-80. · Zbl 0247.60005 · doi:10.1137/1116025 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
