# UCLA Logic Colloquium

The UCLA Logic Colloquium meets on alternate Fridays, at 4 p.m., in MS 6221.
The Logic Colloquium Chair is Artem Chernikov.
Here are links to the UCLA Logic Center, the Caltech-UCLA Logic Seminar, and the Philosophy Colloquium.

Talks are listed here in reverse chronological order.

# Logic Colloquium: 03/21/2019 - 03/20/2020

 Friday May 31 2019 16:00-16:50 (MS 6221) Joshua Wiscons (Sacramento State) TBA Abstract. TBAHide Friday May 17 2019 16:00-16:50 (MS 6221) Rachid Atmai (Mira Costa College, Oceanside) TBA Abstract. TBAHide Friday Apr 19 2019 04:00-04:50 (MS 6221) Todor Tsankov (University Paris 7) TBA Abstract. TBAHide

# Logic Colloquium: 09/1/2014 - 03/20/2019

 Friday Mar 08 2019 16:00-16:50 (MS 6221) Nadja Hempel (UCLA) N-dependent groups and fields Abstract. NIP theories are the first class of the hierarchy of n-dependent structures. The random n-hypergraph is the canonical object which is n-dependent but not (n-1)-dependent. Thus the hierarchy is strict. But one might ask if there are any algebraic objects (groups, rings, fields) which are strictly n-dependent for every n? We will start by introducing the n-dependent hierarchy and present all known results on n-dependent groups and fields.Hide Friday Feb 22 2019 16:00-16:50 (MS 6221) Omer Mermelstein (University of Wisconsin - Madison) Generic flat pregeometries Abstract. The property of "flatness" of a pregeometry (matroid) is best known in model theory as the device with which Hrushovski showed that his example refuting Zilber's conjecture does not interpret an infinite group. I will dedicate the first part of this talk to explaining what flatness is, how it should be thought of, and how closely it relates to hypergraphs and Hrushovski's construction method. In the second part, I will conjecture that the family of flat pregeometries associated to strongly minimal sets is model theoretically nice, and share some intermediate results.Hide Friday Feb 08 2019 16:00-16:50 (MS 6221) Adam Day (Victoria University of Wellington) Computability Theoretic Hierarchies of Real-valued Functions Abstract. In this talk I will review some fundamental concepts in computability theory and show how they can be applied to analyze the relative complexity of real-valued functions. I will review some old results that come from this analysis, in particular, the continuous degrees of Miller. Then I will introduce some new hierarchies that results from joint work with Downey and Westrick. One of these new hierarchies refines the Bourgain rank for Baire class 1 functions and allows a new way to extend this rank to all Baire measurable functions.Hide Friday Jan 25 2019 16:00-16:50 (MS 6221) Lynn Scow (California State University, San Bernardino) Transfer of the Ramsey property Abstract. For $L$-structures $B$, $C$ we use the notation ${C choose B}$ to denote the set of all substructures of $C$ isomorphic to $B$. We say that a countable, locally finite structure $I$ ordered by a relation $<$ has RP (the Ramsey property) if for all $A_0, B_0 in textrm{age}(I)$ and integers $k geq 1$ there is some $C_0 in textrm{age}(I)$ such that $C_0 rightarrow (B_0)^{A_0}_k$. In other words, for all functions $c: {C_0 choose A_0} rightarrow k$ there is some $B' subseteq C_0$, $B' cong B_0$ such that $c$ restricted to ${B' choose A_0}$ is a constant function. We will approach the question of when RP transfers from one countable structure to another, where these structures are in possibly different languages. We will look at universal algebraic and model theoretic criteria.Hide Friday Jan 11 2019 16:00-16:50 (MS 6221) Szymon Torunczyk (University of Warsaw) Some applications of model theory in computer science Abstract. I will present a few basic applications of model theory in theoretical computer science, e.g. in verification, databases, and algorithms. I will also discuss some initial ideas employing (ideas from) stability theory to solve algorithmic problems concerning graphs.Hide Friday Nov 30 2018 16:00-16:50 (MS 6221) Nick Ramsey (UCLA) Kim-independence and NSOP1 theories Abstract. Shelah's work on saturation spectra, Hrushovski on PAC structures, and Cherlin-Hrushovski on quasi-finite structures gave the initial impetus for the development of simple theories. A general theory, which unified and explained these different lines of research, was developed by Kim and Pillay using the notion of non-forking independence, which in turn spawned a remarkably rich line of model-theoretic research. In my talk, we will describe a parallel theory for the broader class of NSOP1 theories centered around the notion of Kim-independence and the applications that this theory made possible. We will survey results in a series of papers joint with Artem Chernikov, Itay Kaplan, Alex Kruckman, and Saharon Shelah (though not all at once).Hide Friday Nov 16 2018 16:00-16:50 (MS 6221) Lynn Scow (California State University, San Bernardino) Transfer of the Ramsey property - CANCELLED Abstract. For $L$-structures $B$, $C$ we use the notation ${C choose B}$ to denote the set of all substructures of $C$ isomorphic to $B$. We say that a countable, locally finite structure $I$ ordered by a relation $<$ has RP (the Ramsey property) if for all $A_0, B_0$ in age$(I)$ and integers $k geq 1$ there is some $C_0$ in age$(I)$ such that $C_0 rightarrow (B_0)^{A_0}_k$. In other words, for all functions $c: {C_0 choose A_0} rightarrow k$ there is some $B' subseteq C_0$, $B' cong B_0$ such that $c$ restricted to ${B' choose A_0}$ is a constant function. We will approach the question of when RP transfers from one countable structure to another, where these structures are in possibly different languages. We will look at universal algebraic and model theoretic criteria.Hide Friday Nov 02 2018 16:00-16:50 (MS 6221) Douglas Ulrich (UC Irvine) Generalized Amalgamation and Chromatic Numbers Abstract. Let $T_{k+1, k}$ denote the theory of the k-ary, k+1-clique free random hypergraph, for k >= 3. Malliaris and Shelah have famously proven that $T_{k+1, k}$ is not below $T_{k'+1, k'}$ in Keisler's order, whenever k+1 < k'; hence, Keisler's order has infinitely many classes. I have since improved the combinatorics to obtain the same result whenever k < k', and I obtain model-theoretic upper and lower bounds for the relevant dividing lines detected by Keisler's order. These bounds correspond to various kinds of k-dimensional amalgamation properties. The combinatorics involved is rather technical; however, the model-theoretic upper and lower bounds are not. I aim to introduce and motivate them; in particular, we will explore a connection between generalized amalgamation properties and the chromatic numbers of hypergraphs of partial types. It is open if the various k-dimensional amalgamation properties we introduce are equivalent.Hide Friday Oct 19 2018 16:00-16:50 (MS 6221) Sam Buss (UC San Diego) Bounded Arithmetic, Expanders, and Monotone Propositional Proofs Abstract. This talk discusses a new combinatorial proof of the existence of expander graphs, which can be carried out in the bounded arithmetic theory VNC$^1$ corresponding to alternating linear time. As an application, we prove that the monotone propositional sequent calculus polynomially simulates the full propositional sequent calculus. Prior to this, only a quasipolynomial simulation was known. Joint work with Valentine Kabanets, Antonina Kolokolova, and Michal Koucky.Hide Friday Oct 05 2018 16:00-16:50 (MS 6221) Byunghan Kim (Yonsei University, Seoul) On the number of countable NSOP$_1$ theories without weight $omega$. Abstract. Lachlan's problem is asking whether any countable theory $T$ with \$1