A graph has a countable chromatic number if the vertices can be labeled by natural numbers so that no edge has the same label on both ends. Verifying this property for a given graph can be somewhat difficult; consider e.g. the graph of points in the Euclidean space $ℝ^n$ connected with an edge iff their distance is a rational number. The countable chromatic number of this graph is an easy observation for $n=1$, but a nontrivial result for $n>1$ (Komjath, Schmerl). I will introduce an infinite determined game which provides a simple criterion for a definable (analytic on a Polish space) graph to be countably chromatic; it is sufficient to verify that the second player has a winning strategy. Using this criterion we can e.g. easily resolve the example of $ℝ^n$, as well as deduce interesting consequences on the structure of uncountably chromatic definable graphs.
The talk is based on the paper Chodounský, Zapletal: Two graph games (2024).
Given a topology on the natural numbers, how complicated is it to describe? To answer this question with tools from computability theory, we will restrict to the context of countable second-countable (CSC) topological spaces. One approach is to assign an index to each computable CSC space and determine the arithmetic complexity of the set of CSC spaces with some property. Another approach comes from computable structure theory; for example, given two computable copies of a CSC space, does there exist a computable homeomorphism between them? In this talk, we will explore these approaches and apply them in three running examples: the indiscrete, discrete, and initial segment topologies.
NOTES: the speaker will be online.
I will give a talk on several recent results regarding ultrahomogeneous graphs. A relational structure R is ultrahomogeneous if every isomorphism of finite induced substructures of R extends to an automorphism of R. We classify the finite vertex-colored oriented ultrahomogeneous graphs and the finite vertex-colored undirected graphs. The classifications comprise new general methods which govern how graphs can be combined or extended to create new ultrahomogeneous graphs. Further, we extend a classic theorem of Cameron (every 5-tuple regular graph is already ultrahomogeneous) to the setting of colored graphs.
This is joint work with Sofia Brenner, Eda Kaja, Thomas Schneider, and Pascal Schweitzer.
We shall present a general method of constructing uncountable structures that are homogeneous with respect to their finitely generated substructures. The method is based on the category-theoretic Fraisse limits, using the monoid of self-embeddings of a countable homogeneous structure. Joint work with Adam Bartoš.
Fix a sequence of countable structures $\mathcal{M}_n$, for $n$ in $ℕ$, in a given first-order language $\mathcal{L}$. The reduced product of $(\mathcal{M}_n)$, denoted $\prod_n\mathcal{M}_n/\mathrm{Fin}$ is the $\mathcal{L}$-structure obtained by quotienting the product of the $\mathcal{M}_n$ by the equivalence relation of 'eventual equality'. This is similar to the ultraproduct construction, yet its theory is fairly less understood.
We consider the following question: if two reduced products $\prod_n\mathcal{M}_n/\mathrm{Fin}$ and $\prod_n\mathcal{N}_n/\mathrm{Fin}$ are isomorphic, what can be said about relations between structures we started with? Of course, one can obtain isomorphisms by taking fiberwise isomorphisms, and/or shuffling the indexes, but is that all? We discuss how, in specific interesting cases (such as fields, or certain graphs), answers to this question depend on the set theoretic ambient.
In this talk we investigate what happens when we take concepts from computable structure theory and forbid the use of unbounded search. In other words, we discuss the primitive recursive content of computable structure theory. The central definition is that of punctual structures, introduced by Kalimullin, Melnikov and Ng in 2017. A common theme is that new techniques are required in the primitive recursive analogue of computable structure theory concepts. We also discuss a degree structure within punctual presentations which is induced by primitive recursive isomorphisms. This degree structure is a new concept that does not arise in computable structure theory.
In this talk we will present a 1989 paper of Chatzidakis which consists in the following. In a field of characteristic $p>0$, the Artin-Shreier map $x \mapsto x^p-x$ is an additive homomorphism. Chatzidakis considers and solves the question of the existence of a cross section of the Artin-Shreier map which has a decidable theory, by describing a model-companion. Then she constructs an explicit model within the algebraic closure $𝔽_p^{\textrm{alg}}$ of the prime field. The construction is quite involved and has a gap, and we will propose a fix for that gap, which is joint work with Martin Hils.
The concept of a monster model in model theory is a helpful tool for avoiding cumbersome bookkeeping and notation. Instead of needing to repeatedly take elementary extensions to realise types, or find automorphisms, one can simply say that there is a model M of a theory such that any 'small' model of that theory embeds into M, and any 'small' partial isomorphism in M extends to an automorphism. While usually 'small' means 'cardinality less than M' (and M is then taken to be 'big enough'), sometimes there are special cases in which 'small' means 'set-sized'. In particular, the surreal numbers acts as a monster model for the theory of dense linear orders, real-closed fields, and more.
I will introduce the concept of a monster model and its uses, expand somewhat on the hidden set-theoretic baggage associated with these objects, and show off the monstrosity of the surreal numbers. I will then show how, without the axiom of choice, the surreal numbers may no longer be a monster, using a simple symmetric extension argument.
A splitting family at a regular cardinal kappa is defined so that for any subset X of kappa of size kappa there is a member of the family Y which splits X, namely, both X intersect Y and X - Y have size kappa. The splitting number for kappa is the least size of a splitting family at kappa. Large splitting numbers imply an amount of compactness for kappa (from work of Suzuki). Moreover, forcing can increase the splitting number at supercompact kappa (via Zapletal, credited to Kamo).
I will introduce the stationary splitting number, the least size of a stationary splitting family, which is a family of subsets of kappa splitting stationary subsets into sets that are both stationary. This came up during work with Fuchs on what we call Split Principles, and I will give some background on those, and compare the stationary splitting number to the splitting number and what seems to be known.
