Cutting lemma and Zarankiewicz's problem in distal structures

2016/12/03 by Chernikov, Artem, Galvin, David, Starchenko, Sergei · 2 citations
#03C45 #03C64 #05C35 #05D40 #Combinatorics (math.CO) #Computational Geometry (cs.CG) #FOS: Computer and information sciences #FOS: Mathematics #Logic (math.LO)

paper · doi:10.48550/arxiv.1612.00908

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 [J. Fox, J. Pach, A. Sheffer, A. Suk, and J. Zahl. "A semi-algebraic version of Zarankiewicz's problem"] on the semialgebraic planar Zarankiewicz problem to arbitrary o-minimal structures, in particular obtaining an o-minimal generalization of the Szemerédi-Trotter theorem.

Cited by

• Distinct Distances on Pfaffian Curves
• Dimension theory for the asymptotic couple of the field of logarithmic transseries

Related

• Zarankiewicz bounds from distal regularity lemma
• Regularity lemma for distal structures
• An o-minimal Szemerédi-Trotter theorem
• Improved upper bounds on Zarankiewicz numbers
• A Note on "Regularity lemma for distal structures"