Henson's family of countable homogeneous-universal \(K_n\)-free graphs, \(n\ge 3\), has been widely studied in model theory. Less well studied are the existentially complete, countable universal \(B_{n,3}\)-free graphs, where \(B_{n,3}\) is the graph on \(n + 2\) vertices consisting of a \(K_n\) and a triangle joined at one vertex. These graphs were shown to exist by Komjáth (for \(n = 3\), the "bowtie") and by Cherlin, Shelah and Shi (for \(n \ge 4\)). In this talk, I will describe the structure of these graphs, and present some new and old results, due to myself and others, about their model-theoretic properties.
In this talk I will discuss the notion, invented by Zapletal, of pinned cardinal of an analytic equivalence relation, some of its basic properties, and its interaction with large cardinals.
A topological group \(G\) is said to have the Generic Point Property if the universal minimal flow \(M(G)\) has a generic point, a point whose orbit is comeager. This in turn implies that any minimal \(G\)-flow has a generic point. Angel, Kechris, and Lyons asked the following question, known as the Generic Point Problem: if \(G\) is a Polish group and the universal minimal flow \(M(G)\) is metrizable, does \(G\) have the Generic Point Property? In this talk, we will discuss the case where \(G\) is a closed subgroup of \(S_\infty\); in this case, the answer is affirmative. To show this, we give a new, explicit characterization of the greatest \(G\)-ambit and introduce some new tools in structural Ramsey theory.
A topological group \(G\) is said to have the Generic Point Property if the universal minimal flow \(M(G)\) has a generic point, a point whose orbit is comeager. This in turn implies that any minimal \(G\)-flow has a generic point. Angel, Kechris, and Lyons asked the following question, known as the Generic Point Problem: if \(G\) is a Polish group and the universal minimal flow \(M(G)\) is metrizable, does \(G\) have the Generic Point Property? In this talk, we will discuss the case where \(G\) is a closed subgroup of \(S_\infty\); in this case, the answer is affirmative. To show this, we give a new, explicit characterization of the greatest \(G\)-ambit and introduce some new tools in structural Ramsey theory.
A well-known consequence of classical entropy theory is that if \(G\) is a countable amenable group and \(k < n\) are positive integers, then there does not exist any compact invariant set \(Y\) in \(k^G\) which continuously and equivariantly maps onto \(n^G\). A similar statement holds in the setting of invariant Borel probability measures and measure-preserving equivariant maps. In this talk, I will show that these properties completely fail for all countable non-amenable groups. Specifically, if \(G\) is non-amenable then there is an integer \(k\) with the following property: for any compact metrizable space \(X\) and any continuous action of \(G\) on \(X\), there is a compact invariant set \(Y\) in \(k^G\) which continuously and equivariantly maps onto \(X\). We will also obtain a similar result for invariant probability measures and measure-preserving maps.
For any Polish spaces \(X\) and \(Y\), and for any \(A, B\) subsets of the product \(X\times Y\), we say that \(A\) is separable from \(B\) by a \(\Gamma\times\Gamma'\) set, if there are \(C\in\Gamma(X)\) and \(D\in\Gamma'(Y)\), such that \(A\subseteq C\times D\) and \(B\cap (C\times D) = \emptyset\). We provide an antichain basis, via a suitable reduction, for non-separability of disjoint analytic sets in each of the cases where \(\Gamma, \Gamma' \in \{\mathbf\Sigma^0_1, \mathbf\Pi^0_1, \mathbf\Pi^0_2\}\).
The search for a satisfactory notion of the mutual information between two infinite data streams is a major open problem in algorithmic information theory. This talk discusses our recent solution of a closely related problem, the correct formulation of the mutual dimension (density of shared information) between two points in Euclidean space. We define mutual dimension and show that it satisfies the desiderata for such a quantity, most crucially the data processing inequality, which says that the action of a computable Lipschitz function cannot increase a point's mutual dimension with any other point. Implications for the mutual information between infinite data streams will also be discussed.
This is joint work with Adam Case.
We introduce the dimension spectrum of a subshift \(X\) as \(\{\dim_H(x) : x \in X\}\), where \(\dim_H\) is the effective dimension, and work towards a characterization of the possible dimension spectra. Simpson showed that every dimension spectrum has a top element. We show that the dimension spectrum of a one-dimensional minimal subshift has a least element. Conditions are given under which the dimension spectrum of \(X\) is the interval \([0,\operatorname{ent}(X)]\), and examples are given where the dimension spectrum is bounded away from \(0\). No prior knowledge of subshifts will be assumed.
Solovay proved that if a set \(X\) belongs to a generic extension of a model \(M\) and \(X\) is a subset of \(M\) then the extension is also a generic extension of \(M[X]\). Generalizations of this lemma and related corollaries, for sets \(X\) not necessarily being subsets of \(M\), will be discussed.
I will present a proof of the following: Assume \(\mathsf{OCA}_\infty\) (an apparent strengthening of Todorčević's open colouring axiom which was introduced by Farah) and that all uncountable sets of reals contain a perfect set. Then there are no infinite maximal almost disjoint (mad) families of subsets of the natural numbers. It follows from this that there are no mad families in Solovay's model, which solves a problem posed by Mathias in 1967. If time allows (somewhat unlikely), I will also say something about a more general approach to problems of this sort.
I will present a new rigidity result which gives necessary and sufficient conditions for "translation profinite" actions \(\Gamma\curvearrowright G\) with spectral gap, to be orbit equivalent or Borel reducible.
We study model-theoretic properties of a class of countable structures \(\mathcal K\) that guarantee non-smoothness of the universal \(\mathcal K\)-structurable countable Borel equivalence relation and \(\mathcal K\)-structurable countable group actions.
We study model-theoretic properties of a class of countable structures \(\mathcal K\) that guarantee non-smoothness of the universal \(\mathcal K\)-structurable countable Borel equivalence relation and \(\mathcal K\)-structurable countable group actions.