Ramsey-like theorems for separable permutations
Quentin Le Houérou, Ludovic Patey · 2025
Read Ramsey-like theorems for separable permutations by Quentin Le Houérou, Ludovic Patey (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-07606.txt.
Description
Quentin Le Houérou and Ludovic Patey study a family of math statements in the style of Ramsey theory, in a 2025 paper. Each statement says that any coloring of the links in an endless complete graph leaves a large sub-graph that avoids a set pattern. The authors ask how much computing power each statement needs. One class of patterns, called separable permutations, turns out to play a special role.
For those patterns, avoiding the pattern is shown to match a basic known property: the existence of an endless set that is uniform in color. For every other pattern, that match fails. The proof uses a fresh argument about what cannot be computed, even with extra help allowed. The result draws a sharp line between pattern types that look alike on the surface.
Catalog record
| CREATOR | Quentin Le Houérou, Ludovic Patey |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 146 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-07606