The Galvin-Prikry theorem states that Borel partitions of the Baire space are Ramsey. Thus, given any Borel subset $\chi$ of the Baire space and an infinite set $N$, there is an infinite subset $M$ of $N$ such that $\left [M \right ]^{\omega }$ is either contained in $\chi$ or disjoint from $\chi$ . In their 2005 paper, Kechris, Pestov and Todorcevic point out the dearth of similar results for homogeneous relational structures. We have attained such a result for Borel colorings of copies of the Rado graph. We build a topological space of copies of the Rado graph, forming a subspace of the Baire space. Using techniques developed for our work on the big Ramsey degrees of the Henson graphs, we prove that Borel partitions of this space of Rado graphs are Ramsey.[-]

By the Cantor-Bendixson theorem, subtrees of the binary tree on $\omega$ satisfy a dichotomy - either the tree has countably many branches or there is a perfect subtree (and in particular, the tree has continuum manybranches, regardless of the size of the continuum). We generalize this to arbitrary regular cardinals $\kappa$ and ask whether every $\kappa$-tree with more than $\kappa$ branches has a perfect subset. From large cardinals, this statement isconsistent at a weakly compact cardinal $\kappa$. We show using stacking mice that the existence of a non-domestic mouse (which yields a model with a proper class of Woodin cardinals and strong cardinals) is a lower bound. Moreover, we study variants of this statement involving sealed trees, i.e. trees with the property that their set of branches cannot be changed by certain forcings, and obtain lower bounds for these as well. This is joint work with Yair Hayut.[-]

The productivity of the $\kappa $-chain condition, where $\kappa $ is a regular, uncountable cardinal, has been the focus of a great deal of set-theoretic research. In the 1970's, consistent examples of $kappa-cc$ posets whose squares are not $\kappa-cc$ were constructed by Laver, Galvin, Roitman and Fleissner. Later, ZFC examples were constructed by Todorcevic, Shelah, and others. The most difficult case, that in which $\kappa = \aleph{_2}$, was resolved by Shelah in 1997.
In the first part of this talk, we shall present analogous results regarding the infinite productivity of chain conditions stronger than $\kappa-cc$. In particular, for any successor cardinal $\kappa$, we produce a ZFC example of a poset with precaliber $\kappa$ whose $\omega ^{th}$ power is not $\kappa-cc$. To do so, we introduce and study the principle $U(\kappa , \mu , \theta , \chi )$ asserting the existence of a coloring $c:\left [ \kappa \right ]^{2}\rightarrow \theta $ satisfying a strong unboundedness condition.
In the second part of this talk, we shall introduce and study a new cardinal invariant $\chi \left ( \kappa \right )$ for a regular uncountable cardinal $\kappa$ . For inaccessible $\kappa$, $\chi \left ( \kappa \right )$ may be seen as a measure of how far away $\kappa$ is from being weakly compact. We shall prove that if $\chi \left ( \kappa \right )> 1$, then $\chi \left ( \kappa \right )=max(Cspec(\kappa ))$, where:
(1) Cspec$(\kappa)$ := {$\chi (\vec{C})\mid \vec{C}$ is a sequence over $\kappa$} $\setminus \omega$, and
(2) $\chi \left ( \vec{C} \right )$ is the least cardinal $\chi \leq \kappa $ such that there exist $\Delta\in\left [ \kappa \right ]^{\kappa }$ and
b : $\kappa \rightarrow \left [ \kappa \right ]^{\chi }$ with $\Delta \cap \alpha \subseteq \cup _{\beta \in b(\alpha )}C_{\beta }$ for every $\alpha < \kappa$.
We shall also prove that if $\chi (\kappa )=1$, then $\kappa$ is greatly Mahlo, prove the consistency (modulo the existence of a supercompact) of $\chi (\aleph_{\omega +1})=\aleph_{0}$, and carry a systematic study of the effect of square principles on the $C$-sequence spectrum.
In the last part of this talk, we shall unveil an unexpected connection between the two principles discussed in the previous parts, proving that, for infinite regular cardinals $\theta< \kappa ,\theta \in Cspec(\kappa )$ if there is a closed witness to $U_{(\kappa ,\kappa ,\theta ,\theta )}$.
This is joint work with Chris Lambie-Hanson.[-]

We report on a joint work in progress with Rahman Mohammadpour in which we study the problem of the possible existence of a universal tree under weak embeddings in the classes of $\aleph_{2}$-Aronszajn and wide $\aleph_{2}$-Aronszajn trees. This problem is more complex than previously thought, in particular it seems not to be resolved under ShFA $+$ CH using the technology of weakly Lipshitz trees. We show that under CH, for a given $\aleph_{2}$-Aronszajn tree $\mathrm{T}$ without a weak ascent path, there is an $\aleph_{2^{-\mathrm{C}\mathrm{C}}}$ countably closed forcing forcing which specialises $\mathrm{T}$ and adds an $\aleph_{2}$-Aronszajn tree which does not embed into T. One cannot however apply the ShFA to this forcing.[-]

Two-player turn-based zero-sum games on (finite or infinite) graphs are a central framework in theoretical computer science — notably as a tool for controller synthesis, but also due to their connection with logic and automata theory. A crucial challenge in the field is to understand how complex strategies need to be to play optimally, given a type of game and a winning objective. I will give a tour of recent advances aiming to characterize games where finite-memory strategies suffice (i.e., using a limited amount of information about the past). We mostly focus on so-called chromatic memory, which is limited to using colors — the basic building blocks of objectives — seen along a play to update itself. Chromatic memory has the advantage of being usable in different game graphs, and the corresponding class of strategies turns out to be of great interest to both the practical and the theoretical sides.[-]

This is the story of two distinct approaches for understanding what are 'languages of words', namely 'algebra' and 'logic'. These two approaches eventually rejoined and now irrigate a vivid community of researchers in computer science. In this talk, I will try to give a broad picture of these two perspectives and intuitions on how they nicely interact. An overview:

- The algebraic point of view: words are element in a free algebra.
The first branch, language theory, is concerned with the description of languages of words seen as elements of the free monoid (generated by some finite set traditionally called the alphabet). As such, words are simply terms in some algebra in the sense of universal algebra. After the seminal works of Kleene and Rabin&Scott, that defined the key notion of regular language, this branch developed toward the analysis of the expressive power of restricted formalisms and machines for describing languages. The leading result here is Schützenberger's theorem which states that being definable by a star-free expression is the same as being recognised by an aperiodic monoid: a brilliant algebraic insight. This algebraic description in language theory nowadays catches up with general algebra and category theory, in particular via the use of monads.

- The model-theoretic point of view: words are relational structures.
The second branch, initiated by Büchi, Elgot, and Trakhtenbrot, is the logical point of view. Words are now seen as labelled chains: linear orders equipped with unary predicates (also called monadic). Now logical sentences are used to express properties over these labelled chains. This time MSO logic (monadic second-order logic, ie first-order logic extended with the ability to quantify over monadic predicates = sets) plays the central role, and turns out to be equivalent to regularity over finite words. But, from the point of view of a logician, there is no reason to restrict our attention to finite words: indeed Büchi soon shows the decidability of MSO over omega-words (ie. labelled chains of order type omega). Rabin then proves the remarkable decidability of MSO over the infinite binary tree, and as a consequence the decidability of MSO over the class of all countable linear chains. The composition method was then introduced by Shelah in a seminal work giving another proof of this decidability over countable linear orders, and establishing at the same time undecidability of the MSO theory over the reals: a brilliant model-theoretic insight. These results were then improved by Gurevitch and Shelah, showing decidability over some restricted forms of uncountable chains, and undecidability without extra set theoretic assumptions (the original result relying on CH).

The two branches have progressively converged and are now actively developed in theoretical computer science, in particular in relation with temporal logics, verification, and algorithmic model theory.[-]

In this talk we will survey questions in logic and complexity at the interface between finite model theory, algorithms and database theory. The focus will be on the complexity of the many tasks related to query answering such as deciding if a Boolean query (for example a restricted first-order formula) is true or not in a finite model, counting the size of the answer set or enumerating the results. It will be a survey of some of the tools from complexity measures trough algorithmic methods to conditional lower bounds that have been designed in the domain over the last years.[-]

An atomic class $K$ is the class of atomic first order models of a countable first order theory (assuming there are such models). Under the weak $\mathrm{GCH}$ it had been proved that if such class is categorical in every $\aleph_n$ then it is categorical in every cardinal and is so called excellent. There are results when we assume categoricity for $\aleph_1, \ldots, \aleph_n$. The lecture is on a ZFC result in this direction for $n=1$. More specifically, if $K$ is categorical in $\aleph_1$ and has a model of cardinality $>2^{\aleph_0}$, then it is $\aleph_0$-stable, which implies having stable amalgamation, and is the first case of excellence.
This a work in preparation by J.T. Baldwin, M.C. Laskowski and S. Shelah.[-]