JAF 2025 Prague
Date:
Following the discovery that the infinite version of Ramsey’s theorem for pairs and two colors (\(\mathsf{RT}^2_2\)) escaped a structural phenomenon from reverse mathematics known as the “Big Five”, many other Ramsey-like statements have been studied from a computational and reverse mathematical viewpoint.
In this talk, we will be considering weakenings of \(\mathsf{RT}^2_2\) where, starting from an infinite graph, we search for an infinite subgraph that avoids some fixed pattern (a pattern will be a finite graph). Out of all the possible patterns, we will focus on those encoding permutations. In particular, our work will show the important role played by a certain class of permutation (already known in combinatorics for its many different characterizations) called the separable permutations.
Denoting by \(\mathsf{RT}^2_2(p)\) the statement asserting that the pattern p can be avoided, our main result is that, in omega-models, \(\mathsf{RT}^2_2(p)\) implies \(\mathsf{RT}^2_2\) if and only if p is a separable permutation.
This is joint work with Ludovic Patey.