Ramsey-like theorems for separable permutations
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915381761802240 |
|---|---|
| author | Houérou, Quentin Le Patey, Ludovic |
| author_facet | Houérou, Quentin Le Patey, Ludovic |
| contents | We conduct a computability-theoretic study of Ramsey-like theorems of the form "Every coloring of the edges of an infinite clique admits an infinite sub-clique avoiding some pattern", with a particular focus on transitive patterns. As it turns out, the patterns corresponding to separable permutations play an important role in the computational features of the statement. We prove that the avoidance of any separable permutation is equivalent to the existence of an infinite homogeneous set in standard models, while this property fails for any other pattern. For this, we develop a novel argument for relativized diagonal non-computation. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_07606 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Ramsey-like theorems for separable permutations Houérou, Quentin Le Patey, Ludovic Logic Combinatorics 03D32, 03B30 (Primary) 05D10, 03F30 (Secondary) We conduct a computability-theoretic study of Ramsey-like theorems of the form "Every coloring of the edges of an infinite clique admits an infinite sub-clique avoiding some pattern", with a particular focus on transitive patterns. As it turns out, the patterns corresponding to separable permutations play an important role in the computational features of the statement. We prove that the avoidance of any separable permutation is equivalent to the existence of an infinite homogeneous set in standard models, while this property fails for any other pattern. For this, we develop a novel argument for relativized diagonal non-computation. |
| title | Ramsey-like theorems for separable permutations |
| topic | Logic Combinatorics 03D32, 03B30 (Primary) 05D10, 03F30 (Secondary) |
| url | https://arxiv.org/abs/2507.07606 |