Ramsey expansions completed for all finite S metric spaces
Ramsey expansions of $S$-metric spaces
Discrete Mathematics
Summary
The paper studies special spaces where distances come from a fixed set of positive numbers, called S-metric spaces. Previously, it was only known how to classify these spaces with certain properties, but the authors have now completed the picture for all cases where these spaces can be combined nicely. This helps understand how these spaces behave when expanded to reveal hidden structural patterns called Ramsey expansions. Their work finalizes the classification for all finite S-metric spaces that have a strong combination property.
What this means in practice
- •For mathematicians and combinatorialists: Provides a complete framework for understanding structural expansions in classes of finite metric spaces with restricted distance sets.
- •For theoretical computer scientists: Clarifies when certain finite metric spaces admit canonical expansions useful in algorithmic and model-theoretic contexts.
A theory result. No direct application yet.
Authors
Jan Hubička, Matěj Konečný, Jaroslav Nešetřil, Norbert Sauer
Abstract
Let $S\subseteq \mathbb R^+$ be a subset of positive reals. We say that a metric space is an $S$-metric space if the range of the metric is a subset of $S\cup \{0\}$. In 2007, Delhommé, Laflamme, Pouzet, and Sauer characterized those sets $S$ for which the class of all finite $S$-metric spaces has the amalgamation property. Given an amalgamation class, a natural question is what its Ramsey expansion is. Ramsey expansions are known for classes of $S$-metric spaces for which $S\cup\{0\}$ carries a natural distance monoid structure, for example for $S=\mathbb Q^+$ or when $S$ is topologically closed. In this paper, we extend this result to all amalgamation classes of finite $S$-metric spaces, thereby completing the Ramsey-theoretic classification of amalgamation classes of finite $S$-metric spaces.