Submission date: 19 September 2016

Abstract:

We investigate bounds in Ramsey theorem for relations definable in NIP structures. We generalize a theorem of Bukh and Matoušek [B. Bukh, J. Matoušek. “Erdö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 R, and show that it doesn't hold in R_{\exp}. We also prove an analog for relations definable in the field of 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.

Mathematics Subject Classification: 03C45, 05C35, 05D10, 05C2

Keywords and phrases:

Full text arXiv 1609.05951: pdf, ps.