A classical (complete) type over a set X consists of a set of formulas, potentially involving parameters from X, that can be thought of as a comprehensive description of a possible element of a model containing X. In more general contexts, where dependence on logic and formulas is to be avoided, Galois types offer an elegant alternative: the type of an element a over a model M is identified as the orbit of a under automorphisms of a very large universal model C that fix M pointwise. In recent work, I have tried to transpose Galois types and some of the associated theory and results, to model-like categories which are, nonetheless, not concrete. In particular, I have had success in the context of accessible categories with directed colimits.

The Erdös-Rényi random graph construction can be seen as inducing a probability measure concentrated on the Rado graph that is invariant under arbitrary permutations of the underlying set of vertices. It is natural to ask: Which other countable structures admit such invariant measures? In 2010, Petrov and Vershik provided the first instance of an invariant measure concentrated on Henson´s countable homogeneous-universal triangle-free graph. We provide a characterisation of countable structures that admit invariant measures, in terms of the notion of (group-theoretic) definable closure. This leads to new examples and non-examples, including a complete list of countable homogeneous graphs, directed graphs, and partial orders that satisfy our criterion. Our proof uses infinitary logic to build on Petrov and Vershik´s constructions, which involve sampling from certain continuum-sized objects. In the case when the measure is concentrated on a graph, these continuum-sized objects are in fact ´graph limits´ in the sense of Lovasz and Szegedy (2006). Joint work with Nathanael Ackerman and Cameron Freer.

Ramsey's theorem states that each coloring has an infinite homogeneous set, but these sets can be arbitrarily spread out. Paul Erdos and Fred Galvin proved that for each coloring f, there is an infinite set that is "packed together" which is given "a small number" of colors by f. In this talk, we will give the precise statement of this packed Ramsey's theorem, and discuss its computational and reverse mathematical strength. We will also introduce a related combinatorial principle called RKL which combines features of Weak K onig's Lemma and Ramsey's Theorem. We will give a precise statement of this principle and two of its generalizations, and discuss their reverse mathematical strength.

The subject of this year’s special programme at the IAS has been Univalent Foundations, aka Homotopy Type Theory — a somewhat radical new approach to working in dependent type theories (specifically, Martin-Löf’s Intensional Type Theory and relatives), informed by ideas from homotopy theory and higher category theory. In this talk, I will briefly introduce the key ideas of the approach for those who have not seen them before, and survey the recent progress that has been made during the special year — ideas and results including new familes of axioms and type-constructors (Univalence and Higher Inductive Types), a better understanding of various existing logical constructions in the setting of Intensional Type Theory (sheaf models, gluing models, coherence theorems), and the formalisation of a large amount of homotopy theory “synthetically” in proof assistants such as Agda and Coq.

Consider a random construction (i.e., a map from sequences of bits to countable structures) that almost surely yields a single structure (or models of a particular theory) up to isomorphism. How much algorithmic randomness is needed in the input sequence to obtain that structure (or models of that theory)? We will examine this question for well-known constructions (such as the Erdös-Rényi random graph) and also consider when we can obtain existing notions of randomness (e.g., Martin-Löf or Kurtz) in this way. Preliminary report on joint work with Nate Ackerman.