Ludovic Patey
YOU?
Author Swipe
View article: Ramsey-like theorems and immunities
Ramsey-like theorems and immunities Open
A Ramsey-like theorem is a statement of the form ``For every 2-coloring of $[\mathbb{N}]^2$, there exists an infinite set~$H \subseteq \mathbb{N}$ such that $[H]^2$ avoids some pattern''. We prove that none of these statements are computab…
View article: Ramsey-like theorems for separable permutations
Ramsey-like theorems for separable permutations Open
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 t…
View article: <!--StartFragment --><span class="cf0">The reverse mathematics of Carlson's theorem for located words</span><!--EndFragment -->
<!--StartFragment --><span>The reverse mathematics of Carlson's theorem for located words</span><!--EndFragment --> Open
16 pages
View article: Ramsey-like theorems for the Schreier barrier
Ramsey-like theorems for the Schreier barrier Open
The family of finite subsets $s$ of the natural numbers such that $|s|=1+\min s$ is known as the Schreier barrier in combinatorics and Banach Space theory, and as the family of exactly $ω$-large sets in Logic. We formulate and prove the ge…
View article: Conservation of Ramsey’s theorem for pairs and well-foundedness
Conservation of Ramsey’s theorem for pairs and well-foundedness Open
In this article, we prove that Ramsey’s theorem for pairs and two colors is -conservative over and over . These results improve theorems from Chong, Slaman and Yang [Adv. Math. 308 (2017), pp. 121–141] and Kołodziejczyk and Yokoyama [In s…
View article: Cross-constraint basis theorems and products of partitions
Cross-constraint basis theorems and products of partitions Open
We both survey and extend a new technique from Lu Liu to prove separation theorems between products of Ramsey-type theorems over computable reducibility. We use this technique to show that Ramsey's theorem for $n$-tuples and three colors i…
View article: The reverse mathematics of the pigeonhole hierarchy
The reverse mathematics of the pigeonhole hierarchy Open
The infinite pigeonhole principle for $k$ colors ($\mathsf{RT}_k$) states, for every $k$-partition $A_0 \sqcup \dots \sqcup A_{k-1} = \mathbb{N}$, the existence of an infinite subset~$H \subseteq A_i$ for some~$i < k$. This seemingly trivi…
View article: $Π^0_4$ conservation of Ramsey's theorem for pairs
$Π^0_4$ conservation of Ramsey's theorem for pairs Open
In this article, we prove that Ramsey's theorem for pairs and two colors is a $\forall Π^0_4$ conservative extension of $\mathsf{RCA}_0 + \mathsf{B}Σ^0_2$, where a $\forall Π^0_4$ formula consists of a universal quantifier over sets follow…
View article: $Π^0_4$ conservation of the Ordered Variable Word theorem
$Π^0_4$ conservation of the Ordered Variable Word theorem Open
A left-variable word over an alphabet~$A$ is a word over~$A \cup \{\star\}$ whose first letter is the distinguished symbol~$\star$ standing for a placeholder. The Ordered Variable Word theorem ($\mathsf{OVW}$), also known as Carlson-Simpso…
View article: The weakness of the Erdős-Moser theorem under arithmetic reductions
The weakness of the Erdős-Moser theorem under arithmetic reductions Open
The Erdős-Moser theorem $(\mathsf{EM})$ says that every infinite tournament admits an infinite transitive subtournament. We study the computational behavior of the Erdős-Moser theorem with respect to the arithmetic hierarchy, and prove tha…
View article: THE REVERSE MATHEMATICS OF ${\mathsf {CAC\ FOR\ TREES}}$
THE REVERSE MATHEMATICS OF ${\mathsf {CAC\ FOR\ TREES}}$ Open
${\mathsf {CAC\ for\ trees}}$ is the statement asserting that any infinite subtree of $\mathbb {N}^{<\mathbb {N}}$ has an infinite path or an infinite antichain. In this paper, we study the computational strength of this theorem from a rev…
View article: PARTITION GENERICITY AND PIGEONHOLE BASIS THEOREMS
PARTITION GENERICITY AND PIGEONHOLE BASIS THEOREMS Open
There exist two main notions of typicality in computability theory, namely, Cohen genericity and randomness. In this article, we introduce a new notion of genericity, called partition genericity , which is at the intersection of these two …
View article: The reverse mathematics of Carlson's theorem for located words
The reverse mathematics of Carlson's theorem for located words Open
In this article, we give two proofs of Carlson's theorem for located words in~$\mathsf{ACA}^+_0$. The first proof is purely combinatorial, in the style of Towsner's proof of Hindman's theorem. The second uses topological dynamics to show t…
View article: Carlson-Simpson's lemma and applications in reverse mathematics
Carlson-Simpson's lemma and applications in reverse mathematics Open
We study the reverse mathematics of infinitary extensions of the Hales-Jewett theorem, due to Carlson and Simpson. These theorems have multiple applications in Ramsey's theory, such as the existence of finite big Ramsey numbers for the tri…
View article: The Reverse Mathematics of CAC for trees
The Reverse Mathematics of CAC for trees Open
CAC for trees is the statement asserting that any infinite subtree of $\mathbb{N}^{<\mathbb{N}}$ has an infinite path or an infinite antichain. In this paper, we study the computational strength of this theorem from a reverse mathematical …
View article: Partition genericity and pigeonhole basis theorems
Partition genericity and pigeonhole basis theorems Open
There exist two notions of typicality in computability theory, namely, genericity and randomness. In this article, we introduce a new notion of genericity, called partition genericity, which is at the intersection of these two notions of t…
View article: THE REVERSE MATHEMATICS OF THE THIN SET AND ERDŐS–MOSER THEOREMS
THE REVERSE MATHEMATICS OF THE THIN SET AND ERDŐS–MOSER THEOREMS Open
The thin set theorem for n -tuples and k colors ( $\operatorname {\mathrm {\sf {TS}}}^n_k$ ) states that every k -coloring of $[\mathbb {N}]^n$ admits an infinite set of integers H such that $[H]^n$ avoids at least one color. In this paper…
View article: Computing sets from all infinite subsets
Computing sets from all infinite subsets Open
International audience
View article: The reverse mathematics of the Thin set and Erdős-Moser theorems
The reverse mathematics of the Thin set and Erdős-Moser theorems Open
The thin set theorem for $n$-tuples and $k$ colors ($\mathsf{TS}^n_k$) states that every $k$-coloring of $[\mathbb{N}]^n$ admits an infinite set of integers $H$ such that $[H]^n$ avoids at least one color. In this paper, we study the combi…
View article: Computing sets from all infinite subsets
Computing sets from all infinite subsets Open
A set is introreducible if it can be computed by every infinite subset of itself. Such a set can be thought of as coding information very robustly. We investigate introreducible sets and related notions. Our two main results are that the c…
View article: RELATIONSHIPS BETWEEN COMPUTABILITY-THEORETIC PROPERTIES OF PROBLEMS
RELATIONSHIPS BETWEEN COMPUTABILITY-THEORETIC PROPERTIES OF PROBLEMS Open
A problem is a multivalued function from a set of instances to a set of solutions . We consider only instances and solutions coded by sets of integers. A problem admits preservation of some computability-theoretic weakness property if ever…
View article: The weakness of the pigeonhole principle under hyperarithmetical reductions
The weakness of the pigeonhole principle under hyperarithmetical reductions Open
The infinite pigeonhole principle for 2-partitions ([Formula: see text]) asserts the existence, for every set [Formula: see text], of an infinite subset of [Formula: see text] or of its complement. In this paper, we study the infinite pige…
View article: Milliken's tree theorem and its applications: a computability-theoretic perspective
Milliken's tree theorem and its applications: a computability-theoretic perspective Open
Milliken's tree theorem is a deep result in combinatorics that generalizes a vast number of other results in the subject, most notably Ramsey's theorem and its many variants and consequences. Motivated by a question of Dobrinen, we initiat…
View article: COH, SRT22, and multiple functionals
COH, SRT22, and multiple functionals Open
We prove the following result: there is a family [Formula: see text] of subsets of ω such that for every stable coloring [Formula: see text] hyperarithmetical in R and every finite collection of Turing functionals, there is an infinite hom…
View article: Some results concerning the SRT 2 2 vs. COH problem
Some results concerning the SRT 2 2 vs. COH problem Open
The $\\mathsf{SRT}^2_2$ vs.\\ $\\mathsf{COH}$ problem is a central problem in\ncomputable combinatorics and reverse mathematics, asking whether every Turing\nideal that satisfies the principle $\\mathsf{SRT}^2_2$ also satisfies the\nprinci…
View article: Ramsey’s theorem and products in the Weihrauch degrees
Ramsey’s theorem and products in the Weihrauch degrees Open
We study the positions in the Weihrauch lattice of parallel products of various combinatorial principles related to Ramsey’s theorem. Among other results, we obtain an answer to a question of Brattka, by showing that Ramsey’s theorem for p…
View article: SRT22 does not imply RT22 in omega-models
SRT22 does not imply RT22 in omega-models Open
We complete a 40-year old program on the computability-theoretic analysis of Ramsey's theorem, starting with Jockusch in 1972, and improving a result of Chong, Slaman and Yang in 2014. Given a set $X$, let $[X]^n$ be the collection of all …