# Caltech–UCLA Logic Seminar

## (Aka Cabal Seminar)

The Logic seminar generally meets on Fridays, 2–3:30p.m., at Caltech or UCLA. Contact Alexander Kechris or Itay Neeman if you wish to give a talk.

Schedule of talks, going back to Fall 2015, in reverse chronological order:

# Logic Seminar: 09/1/2015 - 08/23/2017

 Friday Jun 09 2017 14:00-15:30 (MS 6221) Danny Nguyen (UCLA) Complexity of short Presburger arithmetic Abstract. We study complexity of short sentences in Presburger arithmetic. Here by "short" we mean sentences with a bounded number of variables, quantifiers, inequalities and Boolean operations; the input consists only of the integers involved in the inequalities. The problem is motivated by the earlier work on counting integer points in polytopes and their projections in spaces of bounded dimension. We completely resolve the problem. There were some surprises along the way which we also explain. Joint work with Igor Pak.Hide Friday Jun 02 2017 14:00-15:30 (MS 6221) Anush Tserunyan (UIUC) Ergodic hyperfinite decomposition of countable Borel equivalence relations Abstract. A countable Borel equivalence relation $E$ on a probability space can always be generated in two ways: as the orbit equivalence relation of a Borel action of a countable group and as the connectedness relation of a locally countable Borel graph, called a graphing of $E$. When $E$ is measure-preserving, graphings provide a numerical invariant called cost, whose theory has been largely developed and used by Gaboriau and others in establishing rigidity results. A well-known theorem of Hjorth states that when $E$ is ergodic, treeable (admits an acyclic graphing), and has integer or infinite cost $n \le \infty$, then it is generated by an a.e. free measure-preserving action of the free group $\mathbf{F}_n$ on $n$ generators. We give a simpler proof of this theorem and a further development of our technique yields a strengthening of Hjorth's theorem: the action of $\mathbf{F}_n$ can be arranged so that each of the $n$ generators alone acts ergodically. This is joint work with Benjamin Miller.Hide Friday May 26 2017 14:00-15:30 (MS 6221) Igor Pak (UCLA) Complexity of short generating functions Abstract. Short generating functions (GF) are power series defined as sums of terms $ct^k/(1-t^a)(1-t^b)\dots$. One can think of each term as a GF of a generalized arithmetic progression. The size of a short GF $A(t)$ is defined as the total bit length of the parameters $a,b,c,k,\dots$. We study the problem whether a given GF has a short GF presentation of polynomial size. This turn out to be a hard problem both mathematically and computationally. We resolve it modulo some complexity assumptions. Notably, we show that the truncated theta function $\sum_{k 0$, then $G$ admits a partition into $\epsilon$-Folner sets such that up to translation, only finitely many distinct parts appear. We establish a strengthening of this result for measurable quasitilings of free measure preserving actions of amenable groups. Our proof uses a measurable matching lemma of Lyons and Nazarov that we adapt to an asymmetric context. This is joint work with Conley, Jackson, Kerr, Seward, and Tucker-Drob. (Note unusual time, 3pm.)Hide Friday May 20 2016 13:00-13:50 (MS 3915A) Anton Bobkov (UCLA) VC-density in an additive reduct of p-adic numbers. Abstract. I will introduce basic techniques and results for working with p-adic numbers in model theory, define an additive reduct of p-adic numbers and compute its VC-density function. (Note unusual time, 1pm, and place.)Hide Friday May 13 2016 15:00-15:50 (MS 3915A) Anton Bobkov (UCLA) VC-density in partial order trees. Abstract. I will define notion of VC-density, introduce basic techniques for its computation and show an application to partial order trees. (Note unusual time, 3pm, and place.)Hide Friday Apr 29 2016 15:00-15:50 (MS 6221) Omer Ben Neria (UCLA) The distance between HOD and V Abstract. The pursuit of better understanding the universe of set theory V motivated an extensive study of definable inner models M whose goal is to serve as good approximations to V. A common property of these inner models is that they are contained in HOD, the universe of hereditarily ordinal definable sets. Motivated by the question of how ?close? HOD is to V, we consider various related forcing methods and survey known and new results. This is a joint work with Spencer Unger. (Note unusual time, 3pm.)Hide Friday Apr 15 2016 15:00-15:50 (MS 6221) Spencer Unger (UCLA) Compactness in graphs Abstract. We survey various constants related to colorings of graphs and their compactness properties. We are particularly interested in successors of singulars where we extend techniques for the chromatic number from countable to uncountable cofinalities. (Note unusual time, 3pm.)Hide Friday Apr 01 2016 13:00-13:50 (MS 6221) James Freitag (UCLA) Elimination of imaginaries in ACVF Abstract. We will continue to follow Johnson's exposition of elimination of imaginaries in algebraically closed valued fields. (Note unusual time, 1pm.)Hide Friday Mar 11 2016 14:00-15:30 (MS 6221) Javier de la Nuez (U. Muenster) Bounding the Shelah rank of varieties over the free group Abstract. We report on joint work in progress with Chloé Perin and Rizos Sklinios, where we deduce lower bounds for the Shelah rank of certain definable sets in the free group. In the proof some results from geometric group theory concerning the action of the mapping class group of a surface on its complex of curves come into play.Hide Wednesday Mar 09 2016 16:00-17:30 (MS 5118) Andre Nies (University of Auckland) The complexity of isomorphism between profinite groups Abstract. A topological group $G$ is profinite if it is compact and totally disconnected. Equivalently, $G$ is the inverse limit of a surjective system of finite groups carrying the discrete topology. An example is the additive group of 2-adic integers. We discuss how to represent a countably based profinite group as a point in a Polish space. Thereafter, we study the complexity of their isomorphism using the theory of Borel reducibility in descriptive set theory. For topologically finitely generated groups this complexity is the same as the one of identity for reals. In general, it is the same as the complexity of isomorphism for countable graphs. Note unusual time (4pm), day (Wednesday), and room (MS 5118).Hide Friday Mar 04 2016 14:00-15:30 (MS 6221) James Freitag (UCLA) Elimination of imaginaries for ACVF. Abstract. We will continue working on Johnson's exposition of elimination of imaginaries in ACVF.Hide Friday Feb 19 2016 14:00-15:30 (MS 6221) Noah Schweber (UC Berkeley) Uncountable computable structure theory Abstract. We will examine an approach to studying uncountable structures from a computability-theoretic viewpoint, by looking at generic extensions where those structures become countable. We will prove some basic and general results, and then turn to specific examples, especially of structures which compute every real. We will finally turn to an application of this approach to classical computable structure theory: the Medvedev degrees of countable ordinals.Hide Friday Feb 05 2016 14:00-15:30 (MS 6221) James Freitag (UCLA) Elimination of imaginaries for ACVF: definable types Abstract. We are in the middle of a series of seminars working towards Johnson's exposition of the proof of elimination of imaginaries in algebraically closed valued fields (ACVF). This seminar will be self-contained, and will introduce some general notions around definable types which are used later in the proof.Hide Friday Jan 29 2016 14:00-15:30 (MS 6221) Martino Lupini (Caltech) Nonstandard analysis and a sumset conjecture of Erdos Abstract. It is an open problem to formulate and prove a density version of Hindman's theorem on sets of finite products. I will discuss some results in this direction, which can be naturally presented and proved using the language of nonstandard analysis. This is joint work with Mauro Di Nasso, Isaac Golbring, Renling Jin, Steven Leth, and Karl Mahlburg.Hide Friday Jan 22 2016 14:00-15:30 (MS 6221) Katrin Tent (Universitaet Muenster) Profinite groups with NIP theory and $p$-adic analytic groups Abstract. We consider profinite groups as $2$-sorted structures reflecting the profinite topology. It is shown that if the basis consists of all open subgroups, then the first order theory of such a structure is NIP (that is, does not have the independence property) precisely if the group has a normal subgroup of finite index which is a direct product of finitely many compact $p$-adic analytic groups, for distinct primes $p$. In fact, the condition NIP can here be weakened to NTP${}_2$. We also show that any NIP profinite group, presented as a $2$-sorted structure, has an open prosoluble normal subgroup. (Joint work with D. Machperson.)Hide Friday Jan 15 2016 14:00-15:30 (MS 6221) Alex Kruckman (UC Berkeley) Properly Ergodic Structures Abstract. One natural notion of "random L-structure" is a probability measure on the space of L-structures with domain $\omega$ which is invariant and ergodic for the natural action of $S_\infty$ on this space. We call such measures "ergodic structures." Ergodic structures arise as limits of sequences of finite structures which are convergent in the appropriate sense, generalizing the graph limits (or "graphons") of Lovász and Szegedy. In this talk, I will address the properly ergodic case, in which no isomorphism class of countable structures is given measure 1. In joint work with Ackerman, Freer, and Patel, we give a characterization of those theories (in any countable fragment of $L_{\omega_1,\omega})$ which admit properly ergodic models. The main tools are a Morley-Scott analysis of an ergodic structure, the Aldous-Hoover representation theorem, and an "AFP construction" - a method of producing ergodic structures via inverse limits of discrete probability measures on finite structures.Hide Friday Jan 08 2016 14:00-15:30 (MS 6221) Dima Sinapova (UIC) The tree property at successive cardinals Abstract. The tree property is a reflection type combinatorial principle. It holds at $\omega$ (Konig's infinity lemma), fails at $\omega_1$ (Aronszajn) and can consistently hold at $\omega_2$ (Mitchell). A long standing project in set theory is to obtain the tree property at every regular cardinal greater than $\omega_1$. We will start by introducing some classical results. Then I will show that assuming large cardinals, one can consistently get the tree property at the first and double successor of a singular strong limit cardinal.Hide Friday Dec 04 2015 14:00-15:30 (MS 6221) Artem Chernikov (UCLA) Elimination of imaginaries in algebraically closed valued fields, IV Abstract. This is the 4th in a series of lectures on Johnson's exposition of Hrushovski's simplified proof of elimination of imaginaries for algebraically closed valued fields (ACVF). This time we start working towards the proof and discuss geometric sorts, definable valued vector spaces and submodules, and definable types in ACVF.Hide Friday Nov 20 2015 14:00-15:30 (MS 6221) Peter Burton (Caltech) Completely positive entropy actions of sofic groups with $\mathbb{Z}$ in their center Abstract. Let $\Gamma$ be a sofic group with a copy of $\mathbb{Z}$ in its center. We construct an uncountable family of pairwise nonisomorphic measure-preserving $\Gamma$ actions with completely positive entropy, none of which is a factor of a Bernoulli shift. Our construction shows that the relation of isomorphism among completely positive entropy $\Gamma$ actions is not smooth, in contrast with the relation of isomorphism among Bernoulli shifts.Hide Friday Nov 13 2015 16:00-17:00 (MS 6627) Nick Ramsey (UC Berkeley) Trees and the global combinatorics of first-order theories Abstract. (Note unusual time and place: 4pm in MS 6627.) Model-theoretic tree properties - the tree property (TP), the tree property of the first kind (TP_1), and the tree property of the second kind (TP_2) - provide a way of distinguishing theories based on the complexity of patterns of forking that occur in some formula. These properties have emerged as markers of important dividing lines within model theory. They were introduced by Shelah as the local versions of a family of cardinal invariants quantifying the complexity of forking for a theory, possibly among families of different formulas. Shelah proved a family of results about these tree properties and asked whether certain global analogues of these results might also hold for the cardinal invariants. We will describe how two unexpected tools from infinitary combinatorics - strong colorings studied by Galvin and later Shelah, as well as finite square principles studied by Kennedy and Shelah - can be applied to understand what relationships that hold between the local' tree properties also holds for the global' cardinal invariants.Hide 14:00-15:30 (MS 6221) Jesse Han; Artem Chernikov (UCLA) Basic model theory of algebraically closed valued fields, III Abstract. This is the 3rd in a series of lectures on Johnson's exposition of Hrushovski's simplified proof of elimination of imaginaries for algebraically closed valued fields (ACVF). We will finish the overview of the basic theory of imaginaries, and start setting up the scene for the analysis of ACVF (some combinatorial properties of definable sets, geometric sorts, definable valued vector spaces and modules).Hide Friday Nov 06 2015 14:00-15:30 (MS 6221) Artem Chernikov (UCLA) Regularity lemmas for definable graphs Abstract. Szemeredi regularity lemma is a fundamental result in graph combinatorics with numerous applications in additive number theory, computer science and other fields. Roughly speaking, it asserts that every large enough graph can be partitioned into boundedly many sets so that on almost all pairs of those sets the edges are approximately uniformly distributed at random. It was demonstrated by Gowers that in general the size of the required partition grows as an exponential tower in terms of the allowed error. Recently several improved regularity lemmas giving much better bounds were obtained for restricted families of graphs: algebraic graphs of bounded complexity in large finite fields (Tao), semialgebraic graphs of bounded complexity (Fox, Gromov, Lafforgue, Naor, Pach), graphs of bounded VC-dimension (Lovasz, Szegedy), graphs without arbitrary large half-graphs (i.e. stable graphs, Malliaris, Shelah). It turns out that these results are closely related to the model-theoretic classification theory, Shelah's stability and its generalizations. I will give a survey of the area stressing this point and present some recent joint work with Sergei Starchenko on generalizations of the semialgebraic and stable cases to general NIP structures.Hide Friday Oct 30 2015 14:00-15:30 (MS 6221) Matthias Aschenbrenner, Jesse Han (UCLA) Basic model theory of algebraically closed valued fields, II; imaginaries Abstract. This is the second in a series of lectures on Johnson's exposition of Hrushovski's simplified proof of elimination of imaginaries for algebraically closed valued fields. We will finish the proof of quantifier elimination for algebraically closed valued fields, and then introduce the definition and basic facts concerning imaginaries.Hide Friday Oct 23 2015 14:00-15:30 (MS 6221) James Freitag (UCLA) Around Jouanolou-type theorems Abstract. In the late 1970s, Jouanolou proved that a codimension one holomorphic foliation on a complex manifold (satisfying some technical conditions) has infinitely many hypersurface solutions if and only if it has a meromorphic first integral. This notation will be explained at the beginning of the talk. Around 20 years ago, Hrushovski built on a theorem of Jouanolou concerning hypersurface solutions to Pfaffian equations in order to prove that any differential variety with constant coefficients has either finitely many co-order one subvarieties or admits a nontrivial differential rational map to the constant field. Hrushovski's generaliation of Jouanolou's theorem allowed for a strong characterization of the possible algebraic relations between solutions of any order one ODE. In model theoretic terms, Hrushovski showed that any strongly minimal order one ODE is either nonorthogonal to the constants or has a trivial countably categorical forking geometry. In this talk, I will explain several generalizations of Hrushovski's theorem. The first direction removes the assumption of constant coefficients, while the second generalizes the work to the case of several derivations. I will also explain how these generalizations allow one to answer a question of Hrushovski and Scanlon regarding Lascar rank and Morley rank in differential fields.Hide Friday Oct 16 2015 14:00-15:30 (MS 6221) Matthias Aschenbrenner (UCLA) Basic model theory of algebraically closed valued fields Abstract. This is the first in a series of lectures on Johnson's exposition of Hrushovski's simplified proof of elimination of imaginaries for algebraically closed valued fields. In this introductory talk I will give a crash course in basic valuation theory and prove quantifier elimination for algebraically closed valued fields. No previous knowledge of valuations will be assumed.Hide Friday Oct 09 2015 14:00-15:30 (MS 6221) Martino Lupini (Caltech) Fraisse theory and the noncommutative Poulsen simplex Abstract. The Poulsen simplex is the unique Choquet simplex with dense extreme boundary. It was first realized by Conley and Tornquist that the Poulsen simplex can be obtained via a Fraisse-theoretical construction from a suitable class of linear spaces. In my talk I will recall such a construction, and explain how one can adapt these ideas to define the `quantum analog' of the Poulsen simplex. In conclusion, I will explain how the known equivalent characterizations of the Poulsen simplex can be recovered in the quantum setting.Hide