Abstract
We establish a cutting lemma for definable families of sets in distal structures, as well as the optimality of the distal cell decomposition for definable families of sets on the plane in o-minimal expansions of fields. Using it, we generalize the results in Fox et al. (J Eur Math Soc 19(6):1785–1810, 2017 ) on the semialgebraic planar Zarankiewicz problem to arbitrary o-minimal structures, in particular obtaining an o-minimal generalization of the Szemerédi–Trotter theorem.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Aschenbrenner, M., Dolich, A., Haskell, D., Macpherson, D., Starchenko, S.: Vapnik–Chervonenkis density in some theories without the independence property, II. Notre Dame J. Form. Log. 54(3–4), 311–363 (2013)
Aschenbrenner, M., Dolich, A., Haskell, D., Macpherson, D., Starchenko, S.: Vapnik–Chervonenkis density in some theories without the independence property, I. Trans. Am. Math. Soc. 368(8), 5889–5949 (2016)
Basu, S., Raz, O.E.: An o-minimal Szemerédi–Trotter theorem. Q. J. Math. 69(1), 223–239 (2017)
Bukh, B., Matoušek, J.: Erdős–Szekeres-type statements: Ramsey function and decidability in dimension 1. Duke Math. J. 163(12), 2243–2270 (2014)
Chazelle, B.: Cuttings, Handbook of Data Structures and Applications, pp. 25.1–25.10 (2005)
Chazelle, B., Edelsbrunner, H., Guibas, L.J., Sharir, M.: A singly exponential stratification scheme for real semi-algebraic varieties and its applications. Theor. Comput. Sci. 84(1), 77–105 (1991)
Chernikov, A., Simon, P.: Externally definable sets and dependent pairs II. Trans. Am. Math. Soc. 367(7), 5217–5235 (2015)
Chernikov, A., Starchenko, S.: Model-theoretic Elekes–Szabó in the strongly minimal case, Preprint (2018). arXiv:1801.09301
Chernikov, A., Starchenko, S.: Regularity lemma for distal structures. J. Eur. Math. Soc. 20(10), 2437–2466 (2018)
Clarkson, K.L., Shor, P.W.: Applications of random sampling in computational geometry. II. Discrete Comput. Geom. Int. J. Math. Comput. Sci. 4(5), 387–421 (1989)
Fox, J., Pach, J., Sheffer, A., Suk, A., Zahl, J.: A semi-algebraic version of Zarankiewicz’s problem. J. Eur. Math. Soc. 19(6), 1785–1810 (2017)
Matoušek, J.: Lectures on Discrete Geometry. Graduate Texts in Mathematics. Springer, New York, vol. 212, MR1899299 (2002)
Pach, J., Sharir, M.: Repeated angles in the plane and related problems. J. Comb. Theory Ser. A 59(1), 12–22 (2002)
Simon, P.: Distal and non-distal NIP theories. Ann. Pure Appl. Logic 164(3), 294–318 (2013)
Szemerédi, E., Trotter Jr., W.T.: Extremal problems in discrete geometry. Combinatorica 3(3–4), 381–392 (1983)
Acknowledgements
We thank Shlomo Eshel and the anonymous referee for pointing out some inaccuracies and suggestions on improving the paper. Chernikov was supported by the NSF Research Grant DMS-1600796, by the NSF CAREER grant DMS-1651321 and by an Alfred P. Sloan Fellowship. Galvin was supported by the Simons Foundation. Starchenko was supported by the NSF Research Grant DMS-1500671.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Chernikov, A., Galvin, D. & Starchenko, S. Cutting lemma and Zarankiewicz’s problem in distal structures. Sel. Math. New Ser. 26, 25 (2020). https://doi.org/10.1007/s00029-020-0551-2
Published:
DOI: https://doi.org/10.1007/s00029-020-0551-2