Ramsey growth in some NIP structures

DOI10.1017/S1474748019000100MaRDI QIDQ5147670zbMATH OpenWikidataFDO

Authors Artem Chernikov, S. Starchenko, M. E. M. Thomas

Publication date 27 January 2021

Published in Journal of the Institute of Mathematics of Jussieu (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1609.05951

zbMATH Keywords

\(p\)-minimalityNIPo-minimalitypolynomially boundednessRamsey's theorem

Mathematics Subject Classification ID

Classification theory, stability, and related concepts in model theory (03C45) Model theory of ordered structures; o-minimality (03C64) Models of other mathematical theories (03C65) Extremal problems in graph theory (05C35) Ramsey theory (05D10)

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 [B. Bukh, J. Matouv{s}ek. "ErdH{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 $mathbbR$, 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$.

Recommendations

• Externally definable sets and dependent pairs. II
• Combinatorial complexity in o-minimal geometry
• Uniform bounds on growth in o-minimal structures
• Distality in valued fields and related structures
• Externally definable sets and dependent pairs

Cites work

• A combinatorial problem; stability and order for models and theories in infinitary languages
• A dependent theory with few indiscernibles
• A growth dichotomy for o-minimal expansions of ordered groups
• A Guide to NIP Theories
• A note on the Erdős-Hajnal property for stable graphs
• A version of o-minimality for the p-adics
• Around classification theory of models
• Cell decomposition and classification of definable sets in p-optimal fields
• Classification theory and the number of non-isomorphic models.
• Combinatorial complexity in o-minimal geometry
• Combinatorial Theorems on Classifications of Subsets of a Given Set
• Compression schemes, stable definable families, and o-minimal structures
• Crossing patterns of semi-algebraic sets
• Cutting lemma and Zarankiewicz's problem in distal structures
• Definable functions in tame expansions of algebraically closed valued fields
• Distal and non-distal NIP theories
• Erdős-Hajnal-type results on intersection patterns of geometric objects
• Erdős-Szekeres-type statements: Ramsey function and decidability in dimension 1
• Exponentiation is Hard to Avoid
• Externally definable sets and dependent pairs. II
• Formally p-adic fields
• scientific article; zbMATH DE number 3711961 (Why is no real title available?)
• scientific article; zbMATH DE number 1160037 (Why is no real title available?)
• scientific article; zbMATH DE number 1749054 (Why is no real title available?)
• scientific article; zbMATH DE number 2113455 (Why is no real title available?)
• scientific article; zbMATH DE number 7754034 (Why is no real title available?)
• Hypergraph Ramsey numbers
• Model completeness results for expansions of the ordered field of real numbers by restricted Pfaffian functions and the exponential function
• On definable subsets of p-adic fields
• On NIP and invariant measures
• On Sets of Integers Which Contain No Three Terms in Arithmetical Progression
• On the density of families of sets
• On uniform definability of types over finite sets
• One-Dimensional p -Adic Subanalytic Sets
• Partition relations for cardinal numbers
• Ramsey-type results for semi-algebraic relations
• Regularity lemma for distal structures
• Regularity lemmas for stable graphs
• Sample Compression Schemes for VC Classes
• Some remarks on the theory of graphs
• Strongly dependent theories
• The Erdős-Hajnal conjecture. A survey
• Vapnik-Chervonenkis Classes of Definable Sets
• Vapnik-Chervonenkis density in some theories without the independence property. I

Cited in

(3)

• Partitioning theorems for sets of semi-Pfaffian sets, with applications
• Induced subgraph density. VI: Bounded VC-dimension
• Graph theory. Abstracts from the workshop held January 5--10, 2025

This page was built for publication: Ramsey growth in some NIP structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5147670)