The global Zarankiewicz's problem for hypergraphs asks for an upper bound on the number of edges of a hypergraph, whose edge relation is induced by a fixed hypergraph $E$ that has no sub-hypergraphs of a given size. Basit-Chernikov-Starchenko-Tao-Tran (2021) obtained linear Zarankiewicz bounds in the case of a semilinear $E$, namely $E$ definable in a linear o-minimal structure. We extend this theorem to a broader range of "linear-like" structures, in o-minimal, Presburger arithmetic and stability theoretic settings. Some of the methods involved include (a) a reduction of the problem to the case of arbitrary subgroups $E$ of powers of groups, and (b) an abstract version of Zarankiewicz's problem in the saturated setting.
Joint work with Aris Papadopoulos.
Thatcher and Wright showed that a property of trees of bounded degree is MSO-definable if and only if it is recognizable by a tree-automaton. In this talk we explore the question of when MSO-definability of a property of graphs is equivalent to the existence of a tree automata which, given a suitable expression encoding the input graph, recognizes the property. In this talk, I will survey the state of the art of the "definability equals recognizability" problem. For proving "definability equals recognizability" results the key step is to transduce a suitable tree-like decomposition of the input graph. I will present a new MSO-transduction which forms the core for transducing a particular type of graph decompositions.
The automorphism group $\mathrm{Aut}(A)$ and the monoid of elementary embeddings $\mathrm{EEmb}(A)$ of a first-order structure $A$ are both endowed with a natural topology of pointwise convergence. When $A$ is $\omega$-categorical, these spaces of symmetries (together with their topologies) can be used to reconstruct the original structure up to bi-interpretability. This raises the question of when, given $\mathrm{Aut}(A)$ as a pure group, or $\mathrm{EEmb}(A)$ as a pure monoid, one can reconstruct its topology of pointwise convergence. Whilst the automorphism group version of this problem has been intensively studied over the last 40 years, its analogue for monoids has only recently received attention. In this talk, I will discuss various topological reconstruction problems for monoids of elementary embeddings of $\omega$-categorical structures. We prove that for a countable saturated structure $A$, if $\mathrm{Aut}(A) $ has automatic homeomorphicity with respect to closed subgroups of $S_\omega$ then $\mathrm{EEmb}(A)$ has automatic homeomorphicity with respect to closed submonoids of $\mathbb{N}^{\mathbb{N}}$. This result builds on previous work of Pech and Pech (2018), Behrisch, Truss, and Vargas-García (2017), and Bodirsky, Pinsker, and Pongrácz (2017), who proved special cases of it. We will also discuss when the topology of pointwise convergence ends up being minimal amongst Hausdorff semigroup topologies on $\mathrm{EEmb}(A)$. Interestingly, this seems to happen more easily than for $\mathrm{Aut}(A)$. This talk is based on an upcoming survey paper with Michael Pinsker, and on ongoing work with Javi de la Nuez Gonzalez, Zaniar Ghadernezhad, and Michael Pinsker.
There are many “paradoxical sets” of reals that can be obtained using a well-ordering of the reals or using a non-principal ultrafilter on ℕ, both consequences of the Axiom of Choice. In ZF, can we recover the well-ordering of the reals or the ultrafilter on ℕ from the existence of a given paradoxical set? Under certain amalgamation conditions, we give some negative answers to this question.
NOTES: unusual room and time.
Given an action of a group $G$ on a relational Fraïssé structure $M$, we call this action sharply $k$-homogeneous if, for each isomorphism $f : A \to B$ of substructures of $M$ of size $k$, there is exactly one element of $G$ whose action extends $f$. This generalises the well-known notion of a sharply $k$-transitive action on a set, and was previously investigated by Cameron, Macpherson and Cherlin. I will discuss recent results with J. de la Nuez González which show that a wide variety of Fraïssé structures admit sharply $k$-homogeneous actions for $k \leq 3$ by finitely generated virtually free groups. Our results also specialise to the case of sets, giving the first examples of finitely presented non-split infinite groups with sharply 2-transitive/sharply 3-transitive actions.
The game of cops and robbers is played on a fixed graph, with the cop choosing a vertex to start at, then the robber chooses his, and then they take turns in moving to adjacent vertices. The game ends if the cop captures the robber (lands on its vertex). What graphs allow the cop to have a winning strategy, and how long does the game typically last, assuming optimal play? For finite graphs, the situation is very well understood — the cop-win graphs are precisely constructible graphs (constructed from a single vertex by repeatedly adding dominated vertices), and the capture time can be any finite ordinal (attained for example by finite paths).
In the infinite case, not much is known. In particular, there is no structural characterisation of cop-win graphs. What about the capture time? Is there an ordinal such that for any cop-win graph the sequence of moves of an optimal game is never that ordinal?
In this talk we will explore this question by showing that the answer is surprisingly 'no'.
NOTES: unusual room.
The BSS-RAM model is a logic-based concept that provides a mathematical framework for characterizing algorithms that enable the uniform processing of all finite sequences of individuals in a domain of discourse. The model is machine-oriented and the result of a generalization of several types of abstract machines, such as real RAMs, BSS machines, and deterministic or non-deterministic Turing machines. It was developed on the basis of a concept introduced by Dana Scott and discussed by Egon Börger and others. Individual algorithms can be determined by first-order programs and suitable structures. Each program of a machine is an element of a formal language. Its semantics can be defined by a transition system derived from a suitable first-order structure. The operations of the underlying structure are used to transform objects whereby the transformations themselves can also depend on states and conditions that can be evaluated by means of the relations of the structure.
We survey how initial segments of the Medvedev degrees can be used to interpret the classical propositional calculus, the intuitionistic propositional calculus, and the logic of weak excluded middle.
Set theory has proven useful in the study of derived limits. These functors are widely studied for their applications in algebraic topology, and their behavior is to some extent independent from ZFC. As already shown by Bergfalk and Lambie-Hanson in the case of ordinals, the derived limits associated with some set-theoretic objects tend not to vanish in $𝕃$. This corresponds to some form of incompactness. Here I present a similar nonvanishing result for ${}^κ ω$ that uses diamonds and special Aronszajn trees. This is work in progress with Jeffrey Bergfalk.
