More Like this

1. RAMSEY GROWTH IN SOME NIP STRUCTURES

   https://doi.org/10.1017/S1474748019000100  

   Chernikov, Artem; Starchenko, Sergei; Thomas, Margaret E. (January 2021, Journal of the Institute of Mathematics of Jussieu)

   null (Ed.)

   Abstract We investigate bounds in Ramsey’s theorem for relations definable in NIP structures. Applying model-theoretic methods to finitary combinatorics, we generalize a theorem of Bukh and Matousek ( Duke Mathematical Journal 163 (12) (2014), 2243–2270) from the semialgebraic case to arbitrary polynomially bounded $$o$$ -minimal expansions of $$\mathbb{R}$$ , and show that it does not hold in $$\mathbb{R}_{\exp }$$ . This provides a new combinatorial characterization of polynomial boundedness for $$o$$ -minimal structures. We also prove an analog for relations definable in $$P$$ -minimal structures, in particular for the field of the $$p$$ -adics. Generalizing Conlon et al.  ( Transactions of the American Mathematical Society 366 (9) (2014), 5043–5065), we show that in distal structures the upper bound for $$k$$ -ary definable relations is given by the exponential tower of height $k-1$ . 

   more » « less
2. Monotone T-convex T-differential fields

   https://doi.org/10.2140/mt.2025.4.55  

   Kaplan, Elliot; Pynn-Coates, Nigel (January 2025, Model Theory)

   Let T be a complete, model complete o-minimal theory extending the theory of real closed ordered fields and assume that T is power bounded. Let K be a model of T equipped with a T-convex valuation ring O and a T-derivation ∂ such that ∂ is monotone, i.e., weakly contractive with respect to the valuation induced by O. We show that the theory of monotone T-convex T-differential fields, i.e., the common theory of such K, has a model completion, which is complete and distal. Among the axioms of this model completion, we isolate an analogue of henselianity that we call T∂-henselianity. We establish an Ax-Kochen/Ershov theorem and further results for monotone T-convex T-differential fields that are T∂-henselian. 

   more » « less
3. Model-theoretic Elekes–Szabó in the strongly minimal case

   https://doi.org/10.1142/S0219061321500045  

   Chernikov, Artem; Starchenko, Sergei (August 2021, Journal of Mathematical Logic)

   We prove a generalization of the Elekes–Szabó theorem [G. Elekes and E. Szabó, How to find groups? (and how to use them in Erdos geometry?), Combinatorica 32(5) 537–571 (2012)] for relations definable in strongly minimal structures that are interpretable in distal structures. 

   more » « less
4. A dichotomy for T$$T$$‐convex fields with a monomial group

   https://doi.org/10.1002/malq.202300017  

   Kaplan, Elliot; Kesting, Christoph (November 2023, Mathematical Logic Quarterly)

   Abstract We prove a dichotomy for o‐minimal fields , expanded by a ‐convex valuation ring (where is the theory of ) and a compatible monomial group. We show that if is power bounded, then this expansion of is model complete (assuming that is), it has a distal theory, and the definable sets are geometrically tame. On the other hand, if defines an exponential function, then the natural numbers are externally definable in our expansion, precluding any sort of model‐theoretic tameness. 

   more » « less
5. Crossing the logarithmic barrier for dynamic Boolean data structure lower bounds

   https://doi.org/10.1145/3188745.3188790  

   Larsen, Kasper Green; Weinstein, Omri; Yu, Huacheng (June 2018, STOC 2018 Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing)

   This paper proves the first super-logarithmic lower bounds on the cell probe complexity of dynamic boolean (a.k.a. decision) data structure problems, a long-standing milestone in data structure lower bounds. We introduce a new approach and use it to prove a Ω(log1.5 n) lower bound on the operational time of a wide range of boolean data structure problems, most notably, on the query time of dynamic range counting over F2. Proving an ω(lgn) lower bound for this problem was explicitly posed as one of five important open problems in the late Mihai Pǎtraşcu’s obituary . This result also implies the first ω(lgn) lower bound for the classical 2D range counting problem, one of the most fundamental data structure problems in computational geometry and spatial databases. We derive similar lower bounds for boolean versions of dynamic polynomial evaluation and 2D rectangle stabbing, and for the (non-boolean) problems of range selection and range median. Our technical centerpiece is a new way of “weakly” simulating dynamic data structures using efficient one-way communication protocols with small advantage over random guessing. This simulation involves a surprising excursion to low-degree (Chebyshev) polynomials which may be of independent interest, and offers an entirely new algorithmic angle on the “cell sampling” method of Panigrahy et al. 

   more » « less