1 results
RAMSEY GROWTH IN SOME NIP STRUCTURES
- Part of
-
- Journal:
- Journal of the Institute of Mathematics of Jussieu / Volume 20 / Issue 1 / January 2021
- Published online by Cambridge University Press:
- 19 February 2019, pp. 1-29
- Print publication:
- January 2021
-
- Article
- Export citation
-
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 Journal163(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 Society366(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$.
