Well, Better and In-Between
with Raphaël Carroy. In Well Quasi-orders in Computation, Logic, Language and Reasoning. Ed. Peter Schuster, Monika Seisenberger, Andreas Weiermann, Trends in Logic, Springer. To appear.
Starting from well-quasi-orders (wqos), we motivate step by step the in- troduction of the complicated notion of better-quasi-order (bqo). We then discuss the equivalence between the two main approaches to defining bqo and state several essential results of bqo theory.
After recalling the rˆole played by the ideals of a wqo in its bqoness, we give a new presentation of known examples of wqos which fail to be bqo. We also provide new forbidden pattern conditions ensuring that a quasi-order is a better quasi-order.
Embeddability on functions: order and chaos
with Raphaël Carroy and Zoltán Vidnánszky. Accepted for publication in the Transactions of the AMS. Preprint available on arXiv.org
We study the quasi-order of topological embeddability on definable functions between Polish zero-dimensional spaces. We first study the descriptive complexity of this quasi-order restricted to the space of continuous functions. Our main result is the following dichotomy: the embeddability quasi-order restricted to continuous functions from a given compact space to another is either an analytic complete quasi-order or a well-quasi-order.
We then turn to the existence of maximal elements with respect to embeddability in a given Baire class. It is proved that the class of continuous functions is the only Baire class to admit a maximal element. We prove that no Baire class admits a maximal element, except for the class of continuous functions which admits a maximum element.
Towards better: a motivated introduction to BQO
EMS Surveys in Mathematical Sciences, Volume 4, Issue 2, 2017, pp. 185-218.Preprint available on arXiv.org
The well-quasi-orders (WQO) play an important role in various fields such as Computer Science, Logic or Graph Theory. Since the class of WQOs lacks closure under some important operations, the proof that a certain quasi-order is WQO consists often of proving it enjoys a stronger and more complicated property, namely that of being a better-quasi-order (BQO).
Several articles contains valuable introductory material to the theory of BQOs. However, a textbook entitled "Introduction to better-quasi-order theory" is yet to be written. Here is an attempt to give a motivated and self-contained introduction to the deep concept defined by Nash-Williams that we would expect to find in such a textbook.
Finite versus infinite: an insufficient shift
Advances in Mathematics, 2017, 320 (7), 244-249. Preprint available on arXiv.org
The shift graph is defined on the space of infinite subsets of natural numbers by letting two sets be adjacent if one can be obtained from the other by removing its least element. We show that this graph is not a minimum among the graphs of the form Gf defined on some Polish space X, where two distinct points are adjacent if one can be obtained from the other by a given Borel function f:X→X. This answers the primary outstanding question from (Kechris, Solecki and Todorcevic; 1999).
A Wadge hierarchy for second countable spaces
Archive for Mathematical Logic, 2015, 54 (5), 659–683. The final publication is available at Springer.
We define a notion of reducibility for subsets of a second countable T0 topological space based on, relatively continuous relations and admissible representations. It coincides with Wadge reducibility on zero dimensional spaces. However in virtually every second countable T0 space, it yields a hierarchy on Borel sets, namely it is wellfounded and antichains are of length at most 2. It thus differs from the Wadge reducibility in many important cases, for example on the real line or the Scott Domain P(ω).
From Well to Better, the Space of Ideals
Fundamenta Mathematicae, 2014, 227 (3), 247-270. With Raphaël Carroy. DOI: 10.4064/fm227-3-2
On the one hand, the ideals of a well quasi-order (wqo) naturally
form a compact topological space into which the wqo embeds. On the
other hand, Nash-Williams' barriers are given a uniform structure by
embedding them into the Cantor space.
We prove that every map from a barrier into a wqo restricts
on a barrier to a uniformly continuous map, and therefore extends
to a continuous map from a countable closed subset of the Cantor
space into the space of ideals of the wqo. We then prove that, by
shrinking further, any such continuous map admits a canonical form
with regard to the points whose image is not isolated.
As a consequence, we obtain a simple proof of a result on better
quasi-orders (bqo); namely, a wqo whose set of non principal ideals
is bqo is actually bqo.
Duality and the equational theory of regular languages Future Directions for Logic: Proceedings of PhDs in Logic III. IfColog Proceedings 2. College Publications.
On one hand, the Eilenberg variety theorem establishes a bijective
correspondence between varieties of formal languages and varieties of nite monoids. On the other hand, the Reiterman theorem states that varieties
of finite monoids are exactly the classes of finite monoids definable by
profnite equations. Together these two theorems give a structural insight
in the algebraic theory of finite automata. We explain how duality theory
can account for the combination of this two theorems, as it was pointed
out by (Gehrke, Grigorieff and Pin, 2008).
Better-quasi-order: Ideals and Spaces
2015, PhD advisors: Duparc (Lausanne) and Jean-Éric Pin (CNRS, Paris 7).
Selected undergraduate works
Master thesis (in french), EPFL, July 2010. Pdf
Automates, Langages et Logique
Semester Project (in french), EPFL, Autumn 2009. Pdf
Théorie spectrale et évolution en mécanique quantique
Semester Project (in french), EPFL, Autumn 2008. Pdf