Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

Request Permissions   Purchase Content 
 
 

 

Vapnik-Chervonenkis density in some theories without the independence property, I


Authors: Matthias Aschenbrenner, Alf Dolich, Deirdre Haskell, Dugald Macpherson and Sergei Starchenko
Journal: Trans. Amer. Math. Soc. 368 (2016), 5889-5949
MSC (2010): Primary 03C45, 03C64
DOI: https://doi.org/10.1090/tran/6659
Published electronically: December 22, 2015
MathSciNet review: 3458402
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We recast the problem of calculating Vapnik-Chervonenkis (VC)
density into one of counting types, and thereby calculate bounds (often optimal) on the VC density for some weakly o-minimal, weakly quasi-o-minimal, and $ P$-minimal theories.


References [Enhancements On Off] (What's this?)

  • [1] Khaled A. S. Abdel-Ghaffar, Maximum number of edges joining vertices on a cube, Inform. Process. Lett. 87 (2003), no. 2, 95-99. MR 1983932 (2004d:05100), https://doi.org/10.1016/S0020-0190(03)00257-6
  • [2] H. Adler, Theories controlled by formulas of Vapnik-Chervonenkis codimension $ 1$, preprint (2008).
  • [3] -, An introduction to theories without the independence property, preprint (2008).
  • [4] Martin Anthony, Graham Brightwell, and Colin Cooper, The Vapnik-Chervonenkis dimension of a random graph, 14th British Combinatorial Conference (Keele, 1993), Discrete Math. 138 (1995), no. 1-3, 43-56. MR 1322079 (96b:05156), https://doi.org/10.1016/0012-365X(94)00187-N
  • [5] Matthias Aschenbrenner and Lou van den Dries, Closed asymptotic couples, J. Algebra 225 (2000), no. 1, 309-358. MR 1743664 (2001g:03065), https://doi.org/10.1006/jabr.1999.8128
  • [6] Matthias Aschenbrenner, Alf Dolich, Deirdre Haskell, Dugald Macpherson, and Sergei Starchenko, Vapnik-Chervonenkis density in some theories without the independence property, II, Notre Dame J. Form. Log. 54 (2013), no. 3-4, 311-363. MR 3091661, https://doi.org/10.1215/00294527-2143862
  • [7] Patrice Assouad, Densité et dimension, Ann. Inst. Fourier (Grenoble) 33 (1983), no. 3, 233-282 (French, with English summary). MR 723955 (86j:05022)
  • [8] Patrice Assouad, Observations sur les classes de Vapnik-Cervonenkis et la dimension combinatoire de Blei, Seminar on harmonic analysis, 1983-1984, Publ. Math. Orsay, vol. 85, Univ. Paris XI, Orsay, 1985, pp. 92-112 (French). MR 802778 (87h:62016)
  • [9] John T. Baldwin and Saharon Shelah, Randomness and semigenericity, Trans. Amer. Math. Soc. 349 (1997), no. 4, 1359-1376. MR 1407480 (97j:03065), https://doi.org/10.1090/S0002-9947-97-01869-2
  • [10] József Balogh and Béla Bollobás, Unavoidable traces of set systems, Combinatorica 25 (2005), no. 6, 633-643. MR 2199428 (2006j:05202), https://doi.org/10.1007/s00493-005-0039-x
  • [11] Saugata Basu, Richard Pollack, and Marie-Françoise Roy, On the number of cells defined by a family of polynomials on a variety, Mathematika 43 (1996), no. 1, 120-126. MR 1401711 (97h:14076), https://doi.org/10.1112/S0025579300011621
  • [12] Luc Bélair, Types dans les corps valués munis d'applications coefficients, Illinois J. Math. 43 (1999), no. 2, 410-425 (French, with English summary). MR 1703196 (2000h:03070)
  • [13] Luc Bélair and Michel Bousquet, Types dans les corps valués, C. R. Acad. Sci. Paris Sér. I Math. 323 (1996), no. 8, 841-844 (French, with English and French summaries). MR 1414544 (97e:03054)
  • [14] Oleg Belegradek, Ya'acov Peterzil, and Frank Wagner, Quasi-o-minimal structures, J. Symbolic Logic 65 (2000), no. 3, 1115-1132. MR 1791366 (2001k:03079), https://doi.org/10.2307/2586690
  • [15] Oleg Belegradek, Viktor Verbovskiy, and Frank O. Wagner, Coset-minimal groups, Ann. Pure Appl. Logic 121 (2003), no. 2-3, 113-143. MR 1982944 (2004i:03062), https://doi.org/10.1016/S0168-0072(02)00084-2
  • [16] Garrett Birkhoff, Lattice theory, Third edition. American Mathematical Society Colloquium Publications, Vol. XXV, American Mathematical Society, Providence, R.I., 1967. MR 0227053 (37 #2638)
  • [17] A. Bobkov, VC density for trees, manuscript (2014).
  • [18] H. Brönnimann and M. T. Goodrich, Almost optimal set covers in finite VC-dimension, ACM Symposium on Computational Geometry (Stony Brook, NY, 1994), Discrete Comput. Geom. 14 (1995), no. 4, 463-479. MR 1360948 (96j:68170), https://doi.org/10.1007/BF02570718
  • [19] Enrique Casanovas and Martin Ziegler, Stable theories with a new predicate, J. Symbolic Logic 66 (2001), no. 3, 1127-1140. MR 1856732 (2002k:03050), https://doi.org/10.2307/2695097
  • [20] Gregory Cherlin and Françoise Point, On extensions of Presburger arithmetic, Proceedings of the fourth Easter conference on model theory (Gross Köris, 1986) Seminarberichte, vol. 86, Humboldt Univ., Berlin, 1986, pp. 17-34. MR 884718
  • [21] Artem Chernikov and Pierre Simon, Externally definable sets and dependent pairs, Israel J. Math. 194 (2013), no. 1, 409-425. MR 3047077, https://doi.org/10.1007/s11856-012-0061-9
  • [22] Artem Chernikov and Pierre Simon, Externally definable sets and dependent pairs II, Trans. Amer. Math. Soc. 367 (2015), no. 7, 5217-5235. MR 3335415, https://doi.org/10.1090/S0002-9947-2015-06210-2
  • [23] Raf Cluckers, Analytic $ p$-adic cell decomposition and integrals, Trans. Amer. Math. Soc. 356 (2004), no. 4, 1489-1499. MR 2034315 (2005d:11166), https://doi.org/10.1090/S0002-9947-03-03458-5
  • [24] J. Denef and L. van den Dries, $ p$-adic and real subanalytic sets, Ann. of Math. (2) 128 (1988), no. 1, 79-138. MR 951508 (89k:03034), https://doi.org/10.2307/1971463
  • [25] M. A. Dickmann, Elimination of quantifiers for ordered valuation rings, J. Symbolic Logic 52 (1987), no. 1, 116-128. MR 877859 (88b:03045), https://doi.org/10.2307/2273866
  • [26] Alfred Dolich, John Goodrick, and David Lippel, Dp-minimality: basic facts and examples, Notre Dame J. Form. Log. 52 (2011), no. 3, 267-288. MR 2822489 (2012h:03102), https://doi.org/10.1215/00294527-1435456
  • [27] Lou van den Dries, Tame topology and o-minimal structures, London Mathematical Society Lecture Note Series, vol. 248, Cambridge University Press, Cambridge, 1998. MR 1633348 (99j:03001)
  • [28] Lou van den Dries, Deirdre Haskell, and Dugald Macpherson, One-dimensional $ p$-adic subanalytic sets, J. London Math. Soc. (2) 59 (1999), no. 1, 1-20. MR 1688485 (2000k:03077), https://doi.org/10.1112/S0024610798006917
  • [29] R. M. Dudley, A course on empirical processes, École d'été de probabilités de Saint-Flour, XII--1982, Lecture Notes in Math., vol. 1097, Springer, Berlin, 1984, pp. 1-142. MR 876079 (88e:60029), https://doi.org/10.1007/BFb0099432
  • [30] R. M. Dudley, Uniform central limit theorems, Cambridge Studies in Advanced Mathematics, vol. 63, Cambridge University Press, Cambridge, 1999. MR 1720712 (2000k:60050)
  • [31] Jean-Louis Duret, Les corps faiblement algébriquement clos non séparablement clos ont la propriété d'indépendence, Model theory of algebra and arithmetic (Proc. Conf., Karpacz, 1979), Lecture Notes in Math., vol. 834, Springer, Berlin-New York, 1980, pp. 136-162 (French). MR 606784 (83i:12024)
  • [32] Herbert Edelsbrunner, Algorithms in combinatorial geometry, EATCS Monographs on Theoretical Computer Science, vol. 10, Springer-Verlag, Berlin, 1987. MR 904271 (89a:68205)
  • [33] Gy. Elekes, SUMS versus PRODUCTS in number theory, algebra and Erdős geometry, Paul Erdős and his mathematics, II (Budapest, 1999) Bolyai Soc. Math. Stud., vol. 11, János Bolyai Math. Soc., Budapest, 2002, pp. 241-290. MR 1954729 (2004e:11019)
  • [34] P. Erdös and R. Rado, A partition calculus in set theory, Bull. Amer. Math. Soc. 62 (1956), 427-489. MR 0081864 (18,458a)
  • [35] Z. Füredi and J. Pach, Traces of finite sets: extremal problems and geometric applications, Extremal problems for finite sets (Visegrád, 1991) Bolyai Soc. Math. Stud., vol. 3, János Bolyai Math. Soc., Budapest, 1994, pp. 251-282. MR 1319167 (96c:05182)
  • [36] Vincent Guingona, On uniform definability of types over finite sets, J. Symbolic Logic 77 (2012), no. 2, 499-514. MR 2963018, https://doi.org/10.2178/jsl/1333566634
  • [37] Vincent Guingona and Cameron Donnay Hill, On Vapnik-Chervonenkis density over indiscernible sequences, MLQ Math. Log. Q. 60 (2014), no. 1-2, 59-65. MR 3171609, https://doi.org/10.1002/malq.201300040
  • [38] Y. Gurevich and P. H. Schmitt, The theory of ordered abelian groups does not have the independence property, Trans. Amer. Math. Soc. 284 (1984), no. 1, 171-182. MR 742419 (85g:03053), https://doi.org/10.2307/1999281
  • [39] Jehuda Hartman, The homeomorphic embedding of $ K_{n}$ in the $ m$-cube, Discrete Math. 16 (1976), no. 2, 157-160. MR 0427118 (55 #154)
  • [40] Deirdre Haskell and Dugald Macpherson, Cell decompositions of $ {\rm C}$-minimal structures, Ann. Pure Appl. Logic 66 (1994), no. 2, 113-162. MR 1262433 (95d:03059), https://doi.org/10.1016/0168-0072(94)90064-7
  • [41] Deirdre Haskell and Dugald Macpherson, A version of o-minimality for the $ p$-adics, J. Symbolic Logic 62 (1997), no. 4, 1075-1092. MR 1618009 (99j:03028), https://doi.org/10.2307/2275628
  • [42] Deirdre Haskell and Dugald Macpherson, VC density in real closed valued fields, Prépublications de la séminaire de structures algébriques ordonnées 83 (2008-2009), Equipe de logique, Université Paris VII.
  • [43] David Haussler, Sphere packing numbers for subsets of the Boolean $ n$-cube with bounded Vapnik-Chervonenkis dimension, J. Combin. Theory Ser. A 69 (1995), no. 2, 217-232. MR 1313896 (96f:52027), https://doi.org/10.1016/0097-3165(95)90052-7
  • [44] Wilfrid Hodges, Model theory, Encyclopedia of Mathematics and its Applications, vol. 42, Cambridge University Press, Cambridge, 1993. MR 1221741 (94e:03002)
  • [45] Jan E. Holly, Canonical forms for definable subsets of algebraically closed and real closed valued fields, J. Symbolic Logic 60 (1995), no. 3, 843-860. MR 1348997 (96g:03064), https://doi.org/10.2307/2275760
  • [46] Ehud Hrushovski and David Kazhdan, Integration in valued fields, Algebraic geometry and number theory, Progr. Math., vol. 253, Birkhäuser Boston, Boston, MA, 2006, pp. 261-405. MR 2263194 (2007k:03094), https://doi.org/10.1007/978-0-8176-4532-8_4
  • [47] U. Hrushovski and A. Pillay, Weakly normal groups, Logic colloquium '85 (Orsay, 1985) Stud. Logic Found. Math., vol. 122, North-Holland, Amsterdam, 1987, pp. 233-244. MR 895647 (88e:03051), https://doi.org/10.1016/S0049-237X(09)70556-7
  • [48] Gabriela Jeronimo and Juan Sabia, On the number of sets definable by polynomials, J. Algebra 227 (2000), no. 2, 633-644. MR 1759839 (2002e:68041), https://doi.org/10.1006/jabr.1999.8243
  • [49] H. R. Johnson and M. C. Laskowski, Compression schemes, stable definable families, and o-minimal structures, Discrete Comput. Geom. 43 (2010), no. 4, 914-926. MR 2610477 (2011j:03087), https://doi.org/10.1007/s00454-009-9201-3
  • [50] Itay Kaplan, Alf Onshuus, and Alexander Usvyatsov, Additivity of the dp-rank, Trans. Amer. Math. Soc. 365 (2013), no. 11, 5783-5804. MR 3091265, https://doi.org/10.1090/S0002-9947-2013-05782-0
  • [51] Marek Karpinski and Angus Macintyre, Polynomial bounds for VC dimension of sigmoidal and general Pfaffian neural networks, 1st Annual Dagstuhl Seminar on Neural Computing (1994), J. Comput. System Sci. 54 (1997), no. 1, 169-176. MR 1463257 (98m:68231), https://doi.org/10.1006/jcss.1997.1477
  • [52] Marek Karpinski and Angus Macintyre, Approximating volumes and integrals in o-minimal and $ p$-minimal theories, Connections between model theory and algebraic and analytic geometry, Quad. Mat., vol. 6, Dept. Math., Seconda Univ. Napoli, Caserta, 2000, pp. 149-177. MR 1930686 (2003h:03058)
  • [53] T. Kövari, V. T. Sós, and P. Turán, On a problem of K. Zarankiewicz, Colloquium Math. 3 (1954), 50-57. MR 0065617 (16,456a)
  • [54] K. Zh. Kudaĭbergenov, On the independence property, Sibirsk. Mat. Zh. 41 (2000), no. 1, 134-135, iii (Russian, with Russian summary); English transl., Siberian Math. J. 41 (2000), no. 1, 113. MR 1756481 (2001a:03076), https://doi.org/10.1007/BF02674000
  • [55] K. Zh. Kudaĭbergenov, Weakly quasi-o-minimal models, Mat. Tr. 13 (2010), no. 1, 156-168; English transl., Siberian Adv. Math. 20 (2010), no. 4, 285-292 (Russian, with Russian summary). MR 2682771 (2011k:03072)
  • [56] Franz-Viktor Kuhlmann, Abelian groups with contractions. II. Weak $ {\rm o}$-minimality, Abelian groups and modules (Padova, 1994) Math. Appl., vol. 343, Kluwer Acad. Publ., Dordrecht, 1995, pp. 323-342. MR 1378210 (97g:03044)
  • [57] Michael C. Laskowski, Vapnik-Chervonenkis classes of definable sets, J. London Math. Soc. (2) 45 (1992), no. 2, 377-384. MR 1171563 (93d:03039), https://doi.org/10.1112/jlms/s2-45.2.377
  • [58] Michael C. Laskowski, unpublished notes.
  • [59] L. Lipshitz, Rigid subanalytic sets, Amer. J. Math. 115 (1993), no. 1, 77-108. MR 1209235 (94d:32047), https://doi.org/10.2307/2374723
  • [60] L. Lipshitz and Z. Robinson, One-dimensional fibers of rigid subanalytic sets, J. Symbolic Logic 63 (1998), no. 1, 83-88. MR 1610778 (98m:32049), https://doi.org/10.2307/2586589
  • [61] László Lovász and Balázs Szegedy, Regularity partitions and the topology of graphons, An irregular mind, Bolyai Soc. Math. Stud., vol. 21, János Bolyai Math. Soc., Budapest, 2010, pp. 415-446. MR 2815610 (2012k:05356), https://doi.org/10.1007/978-3-642-14444-8_12
  • [62] Angus Macintyre, On definable subsets of $ p$-adic fields, J. Symbolic Logic 41 (1976), no. 3, 605-610. MR 0485335 (58 #5182)
  • [63] Dugald Macpherson, David Marker, and Charles Steinhorn, Weakly o-minimal structures and real closed fields, Trans. Amer. Math. Soc. 352 (2000), no. 12, 5435-5483 (electronic). MR 1781273 (2001i:03079), https://doi.org/10.1090/S0002-9947-00-02633-7
  • [64] Dugald Macpherson and Charles Steinhorn, On variants of o-minimality, Ann. Pure Appl. Logic 79 (1996), no. 2, 165-209. MR 1396850 (97e:03050), https://doi.org/10.1016/0168-0072(95)00037-2
  • [65] David Marker, Model theory. An introduction, Graduate Texts in Mathematics, vol. 217, Springer-Verlag, New York, 2002. MR 1924282 (2003e:03060)
  • [66] J. Matoušek, Tight upper bounds for the discrepancy of half-spaces, Discrete Comput. Geom. 13 (1995), no. 3-4, 593-601. MR 1318799 (96b:52025), https://doi.org/10.1007/BF02574066
  • [67] Jiří Matoušek, Geometric set systems, European Congress of Mathematics, Vol. II (Budapest, 1996) Progr. Math., vol. 169, Birkhäuser, Basel, 1998, pp. 1-27. MR 1645816 (99j:52025)
  • [68] Jiří Matoušek, Lectures on discrete geometry, Graduate Texts in Mathematics, vol. 212, Springer-Verlag, New York, 2002. MR 1899299 (2003f:52011)
  • [69] Jiří Matoušek, Bounded VC-dimension implies a fractional Helly theorem, Discrete Comput. Geom. 31 (2004), no. 2, 251-255. MR 2060639 (2005d:52011), https://doi.org/10.1007/s00454-003-2859-z
  • [70] Jiří Matoušek, Emo Welzl, and Lorenz Wernisch, Discrepancy and approximations for bounded VC-dimension, Combinatorica 13 (1993), no. 4, 455-466. MR 1262921 (95e:52012), https://doi.org/10.1007/BF01303517
  • [71] Christian Michaux and Roger Villemaire, Presburger arithmetic and recognizability of sets of natural numbers by automata: new proofs of Cobham's and Semenov's theorems, Ann. Pure Appl. Logic 77 (1996), no. 3, 251-277. MR 1370990 (97g:03059), https://doi.org/10.1016/0168-0072(95)00022-4
  • [72] Marie-Hélène Mourgues, Cell decomposition for $ P$-minimal fields, MLQ Math. Log. Q. 55 (2009), no. 5, 487-492. MR 2568759 (2011d:03054), https://doi.org/10.1002/malq.200810009
  • [73] Alf Onshuus and Alexander Usvyatsov, On dp-minimality, strong dependence and weight, J. Symbolic Logic 76 (2011), no. 3, 737-758. MR 2849244 (2012m:03082), https://doi.org/10.2178/jsl/1309952519
  • [74] János Pach and Micha Sharir, Repeated angles in the plane and related problems, J. Combin. Theory Ser. A 59 (1992), no. 1, 12-22. MR 1141318 (92j:52031), https://doi.org/10.1016/0097-3165(92)90094-B
  • [75] János Pach and Micha Sharir, On the number of incidences between points and curves, Combin. Probab. Comput. 7 (1998), no. 1, 121-127. MR 1611057 (99b:52037), https://doi.org/10.1017/S0963548397003192
  • [76] János Pach and Micha Sharir, Geometric incidences, Towards a theory of geometric graphs, Contemp. Math., vol. 342, Amer. Math. Soc., Providence, RI, 2004, pp. 185-223. MR 2065264 (2005e:52026), https://doi.org/10.1090/conm/342/06151
  • [77] Michel Parigot, Théories d'arbres, J. Symbolic Logic 47 (1982), no. 4, 841-853 (1983) (French). MR 683159 (84g:03047), https://doi.org/10.2307/2273103
  • [78] Anand Pillay, The model-theoretic content of Lang's conjecture, Model theory and algebraic geometry, Lecture Notes in Math., vol. 1696, Springer, Berlin, 1998, pp. 101-106. MR 1678531 (2000c:11203), https://doi.org/10.1007/978-3-540-68521-0_6
  • [79] Klaus-Peter Podewski and Martin Ziegler, Stable graphs, Fund. Math. 100 (1978), no. 2, 101-107. MR 0485336 (58 #5183)
  • [80] Françoise Point, On decidable extensions of Presburger arithmetic: from A. Bertrand numeration systems to Pisot numbers, J. Symbolic Logic 65 (2000), no. 3, 1347-1374. MR 1791380 (2002b:03021), https://doi.org/10.2307/2586704
  • [81] Françoise Point and Frank O. Wagner, Essentially periodic ordered groups, Ann. Pure Appl. Logic 105 (2000), no. 1-3, 261-291. MR 1786147 (2002a:03073), https://doi.org/10.1016/S0168-0072(99)00053-6
  • [82] Bruno Poizat, Cours de théorie des modèles (French). Une introduction à la logique mathématique contemporaine. [An introduction to contemporary mathematical logic], Bruno Poizat, Lyon, 1985. MR 817208 (87f:03084)
  • [83] Richard Pollack and Marie-Françoise Roy, On the number of cells defined by a set of polynomials, C. R. Acad. Sci. Paris Sér. I Math. 316 (1993), no. 6, 573-577 (English, with English and French summaries). MR 1212207 (94b:14057)
  • [84] George Pólya and Gabor Szegő, Problems and theorems in analysis. I, Classics in Mathematics, Springer-Verlag, Berlin, 1998. Series, integral calculus, theory of functions; Translated from the German by Dorothee Aeppli; Reprint of the 1978 English translation. MR 1492447
  • [85] Mike Prest, Model theory and modules, London Mathematical Society Lecture Note Series, vol. 130, Cambridge University Press, Cambridge, 1988. MR 933092 (89h:03061)
  • [86] N. Sauer, On the density of families of sets, J. Combinatorial Theory Ser. A 13 (1972), 145-147. MR 0307902 (46 #7017)
  • [87] James H. Schmerl, $ \aleph _{0}$-categorical distributive lattices of finite breadth, Proc. Amer. Math. Soc. 87 (1983), no. 4, 707-713. MR 687647 (85e:03073), https://doi.org/10.2307/2043365
  • [88] James H. Schmerl, Partially ordered sets and the independence property, J. Symbolic Logic 54 (1989), no. 2, 396-401. MR 997874 (90g:06006), https://doi.org/10.2307/2274855
  • [89] Saharon Shelah, Stability, the f.c.p., and superstability; model theoretic properties of formulas in first order theory, Ann. Math. Logic 3 (1971), no. 3, 271-362. MR 0317926 (47 #6475)
  • [90] Saharon Shelah, A combinatorial problem; stability and order for models and theories in infinitary languages, Pacific J. Math. 41 (1972), 247-261. MR 0307903 (46 #7018)
  • [91] 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 (91k:03085)
  • [92] Saharon Shelah, Dependent first order theories, continued, Israel J. Math. 173 (2009), 1-60. MR 2570659 (2011j:03077), https://doi.org/10.1007/s11856-009-0082-1
  • [93] Saharon Shelah, Strongly dependent theories, Israel J. Math. 204 (2014), no. 1, 1-83. MR 3273451, https://doi.org/10.1007/s11856-014-1111-2
  • [94] Saharon Shelah and Joel Spencer, Zero-one laws for sparse random graphs, J. Amer. Math. Soc. 1 (1988), no. 1, 97-115. MR 924703 (89i:05249), https://doi.org/10.2307/1990968
  • [95] Pierre Simon, On dp-minimal ordered structures, J. Symbolic Logic 76 (2011), no. 2, 448-460. MR 2830411 (2012e:03071), https://doi.org/10.2178/jsl/1305810758
  • [96] József Solymosi and Terence Tao, An incidence theorem in higher dimensions, Discrete Comput. Geom. 48 (2012), no. 2, 255-280. MR 2946447, https://doi.org/10.1007/s00454-012-9420-x
  • [97] Joel Spencer, The strange logic of random graphs, Algorithms and Combinatorics, vol. 22, Springer-Verlag, Berlin, 2001. MR 1847951 (2003d:05196)
  • [98] J. Spencer, E. Szemerédi, and W. Trotter Jr., Unit distances in the Euclidean plane, Graph theory and combinatorics (Cambridge, 1983) Academic Press, London, 1984, pp. 293-303. MR 777185 (86m:52015)
  • [99] E. Szemerédi and W. T. Trotter Jr., A combinatorial distinction between the Euclidean and projective planes, European J. Combin. 4 (1983), no. 4, 385-394. MR 743162 (85d:51011), https://doi.org/10.1016/S0195-6698(83)80036-5
  • [100] Csaba D. Tóth, The Szemerédi-Trotter theorem in the complex plane, Combinatorica 35 (2015), no. 1, 95-126. MR 3341142, https://doi.org/10.1007/s00493-014-2686-2
  • [101] V. N. Vapnik and A. Ja. Červonenkis, The uniform convergence of frequencies of the appearance of events to their probabilities, Teor. Verojatnost. i Primenen. 16 (1971), 264-279 (Russian, with English summary). MR 0288823 (44 #6018)
  • [102] Volker Weispfenning, Elimination of quantifiers for certain ordered and lattice-ordered abelian groups, Proceedings of the Model Theory Meeting (Univ. Brussels, Brussels/Univ. Mons, Mons, 1980), 1981, pp. 131-155. MR 620968 (82h:03022)
  • [103] J. Wierzejewski, On stability and products, Fund. Math. 93 (1976), no. 2, 81-95. MR 0429539 (55 #2552)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 03C45, 03C64

Retrieve articles in all journals with MSC (2010): 03C45, 03C64


Additional Information

Matthias Aschenbrenner
Affiliation: Department of Mathematics, University of California, Los Angeles, Box 951555, Los Angeles, California 90095-1555
Email: matthias@math.ucla.edu

Alf Dolich
Affiliation: Department of Mathematics and Computer Science, Kingsborough Community College (CUNY), 2001 Oriental Boulevard, Brooklyn, New York 11235
Address at time of publication: Department of Mathematics, CUNY Graduate Center, 365 5th Avenue, New York, New York 10016
Email: alfredo.dolich@kbcc.cuny.edu

Deirdre Haskell
Affiliation: Department of Mathematics and Statistics, McMaster University, 1280 Main Street W., Hamilton, Ontario L8S 4K1, Canada
Email: haskell@math.mcmaster.ca

Dugald Macpherson
Affiliation: School of Mathematics, University of Leeds, Leeds LS2 9JT, United Kingdom
Email: h.d.macpherson@leeds.ac.uk

Sergei Starchenko
Affiliation: Department of Mathematics, University of Notre Dame, 255 Hurley Building, Notre Dame, Indiana 46556-4618
Email: starchenko.1@nd.edu

DOI: https://doi.org/10.1090/tran/6659
Received by editor(s): December 23, 2011
Received by editor(s) in revised form: December 10, 2014
Published electronically: December 22, 2015
Dedicated: For Lou van den Dries, on his 60th birthday
Article copyright: © Copyright 2015 American Mathematical Society

American Mathematical Society