2019Advances in MathematicsOpen access

All those Ramsey classes (Ramsey classes with closures and forbidden homomorphisms)

Jan Hubička, Jaroslav Nešetřil

Open full text 53 citations

Abstract

We prove the Ramsey property for classes of ordered structures with closures and given local properties. This generalises earlier results: the Nešetřil–Rödl Theorem, the Ramsey property of partial orders and metric spaces as well as the authors' Ramsey lift of bowtie-free graphs. We use this framework to solve several open problems and give new examples of Ramsey classes. Among others, we find Ramsey lifts of convexly ordered S-metric spaces and prove the Ramsey theorem for finite models (i.e. structures with both functions and relations) thus providing the ultimate generalisation of the structural Ramsey theorem. Both of these results are natural, and easy to state, yet their proofs involve most of the theory developed here. We also characterise Ramsey lifts of classes of structures defined by finitely many forbidden homomorphisms and extend this to special cases of classes with closures. This has numerous applications. For example, we find Ramsey lifts of many Cherlin–Shelah–Shi classes.

About this research paper

What this paper is about

We prove the Ramsey property for classes of ordered structures with closures and given local properties. This generalises earlier results: the Nešetřil–Rödl Theorem, the Ramsey property of partial orders and metric spaces as well as the authors' Ramsey lift of bowtie-free graphs. We use this framework to solve several open problems and give new examples of Ramsey classes. Among others, we find Ramsey lifts of convexly ordered S-metric spaces and prove the Ramsey theorem for finite models (i.e. structures with both functions and relations) thus providing the ultimate generalisation of the structural Ramsey theorem. Both of these results are natural, and easy to state, yet their proofs involve most of the theory developed here. We also characterise Ramsey lifts of classes of structures defined by finitely many forbidden homomorphisms and extend this to special cases of classes with closures. This has numerous applications. For example, we find Ramsey lifts of many Cherlin–Shelah–Shi classes.

Why it matters

OpenAlex reports 53 citations for this work. Citation counts describe recorded attention and do not establish research quality.

Key contribution

A contribution statement is not available in the OpenAlex record.

Method / approach

Method details are not available in the OpenAlex metadata.

Main findings

Findings are not separately available in the OpenAlex metadata.

Limitations

Limitations are not available in the OpenAlex metadata.

Applications

Application details are not available in the OpenAlex metadata.

Available abstract

We prove the Ramsey property for classes of ordered structures with closures and given local properties. This generalises earlier results: the Nešetřil–Rödl Theorem, the Ramsey property of partial orders and metric spaces as well as the authors' Ramsey lift of bowtie-free graphs. We use this framework to solve several open problems and give new examples of Ramsey classes. Among others, we find Ramsey lifts of convexly ordered S-metric spaces and prove the Ramsey theorem for finite models (i.e. structures with both functions and relations) thus providing the ultimate generalisation of the structural Ramsey theorem. Both of these results are natural, and easy to state, yet their proofs involve most of the theory developed here. We also characterise Ramsey lifts of classes of structures defined by finitely many forbidden homomorphisms and extend this to special cases of classes with closures. This has numerous applications. For example, we find Ramsey lifts of many Cherlin–Shelah–Shi classes.

Key concepts: Ramsey's theorem, Ramsey theory, Mathematics, Mathematical proof, Homomorphism, Combinatorics, Discrete mathematics, Lift (data mining)

Related papers

Back to paper searchBrowse research topicsOriginal source
All those Ramsey classes (Ramsey classes with closures and forbidden homomorphisms) — Research Paper | ScholarLens