Ramsey growth in some NIP structures
| Autor: | Sergei Starchenko, Artem Chernikov, Margaret E. M. Thomas |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2021 |
| Předmět: |
Polynomial
o-minimality NIP Ramsey's theorem p-minimality polynomially bounded General Mathematics 010102 general mathematics Field (mathematics) Mathematics - Logic 0102 computer and information sciences Characterization (mathematics) Computer Science::Computational Geometry 01 natural sciences Tower (mathematics) Upper and lower bounds 03C45 05C35 05D10 05C2 Combinatorics 010201 computation theory & mathematics Bounded function FOS: Mathematics Mathematics - Combinatorics Finitary Combinatorics (math.CO) 0101 mathematics ddc:510 Logic (math.LO) Mathematics |
| Popis: | 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 [B. Bukh, J. Matou\v{s}ek. "Erd\H{o}s-Szekeres-type statements: Ramsey function and decidability in dimension $1$", 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 doesn't 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 [D. Conlon, J. Fox, J. Pach, B. Sudakov, A. Suk "Ramsey-type results for semi-algebraic relations", 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$. Comment: v.3 26 pages; Section 5 was expanded, providing a discussion of polynomial boundedness in this setting and generalizing the proof to demonstrate that the result applies to P-minimal expansions of fields including analytic expansions and finite extensions of Q_p; minor corrections and presentation improvements were made throughout the article |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|