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

CREATORQuentin Le Houérou, Ludovic Patey
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE146 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-07606

Browse the full library · About the Tower of Babel