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
2016, in ** reverse chronological order**:

Friday Nov 03 2017 | ||||

14:00-15:30 (MS 6221) | Matthew Foreman (UCI) | Classifying diffeomorphisms of the torus | ||

Friday Oct 27 2017 | ||||

14:00-15:30 (MS 6221) | Matthew Foreman (UCI) | Classifying diffeomorphisms of the torus | ||

Friday Oct 13 2017 | ||||

14:00-15:30 (MS 6221) | Kota Takeuchi (University of Tsukuba) | |||

Friday Sep 29 2017 | ||||

14:00-15:30 (MS 6221) | Dana Bartosova (University of Sao Paulo) | Free actions via graphs | ||

Abstract. A topological group admits a free action if there is a
compact space on which it acts without fixed points. We translate this property into colorability of graphs, which leads us to questions of combinatorial nature. This is a joint work in progress with Vladimir Pestov. |

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. | ||||

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. | ||||

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<N} t^{k^2}$ does NOT have a short GF presentation of polynomial size unless #P is in FP/poly. In the talk, I will spend much of the time giving a survey and motivating the problem. I will explain the connections to Presburger arithmetic, integer programming, number theory and discrete geometry. At the end, I will outline the proof. This is joint work with Danny Nguyen. No familiarity with the subject is assumed. | ||||

Friday May 19 2017 | ||||

14:00-15:30 (MS 6221) | Matthew Harrison-Trainor (UC Berkeley) | Describing Finitely Generated Structures | ||

Abstract. Every countable structure has an infinitary sentence which describes it up to isomorphism among countable structures. We can characterize the complexity of a structure by the complexity of the simplest description of that structure. A finitely generated structure always has a $\Sigma_3$ description. We will show that there is a finitely generated group which has no simpler description, and talk about a number of other results of this kind. | ||||

Friday May 12 2017 | ||||

14:00-15:30 (MS 6221) | Wai Yan Pong (CSUDH) | Independence of arithmetic functions | ||

Abstract. We examine various notions of dependence of arithmetic functions via Ax's theorem on differential Schanuel Conjecture. We will sample of several results in the literature and show how they can be generalized. | ||||

Friday Apr 28 2017 | ||||

14:00-15:30 (MS 6221) | Michał Tomasz Godziszewski (University of Warsaw) | Generalizations of Tennebaum phenomena for computable quotient presentations | ||

Abstract. A computable quotient presentation of a mathematical structure $\mathbb{A}$ consists of a computable structure on the natural numbers $(\mathbb{N}, \star, \ast, \ldots)$ (meaning that the operations and relations of the structure are computable) and an equivalence relation $E$ on $\mathbb{N}$, not necessarily computable but which is a congruence with respect to this structure, such that the quotient $(\mathbb{N}, \star, \ast, \ldots)_{/E}$ is isomorphic to the given structure
$\mathbb{A}$. Thus, one may consider computable quotient presentations of graphs, groups, orders, rings and so on, for any kind of mathematical structure.
In 2016 Bakhadyr Khoussainov outlined a sweeping vision for the use of computable quotient presentations as a fruitful alternative approach to the subject of computable model theory. He outlined a program of guiding questions and results in this emerging area. Part of this program concerns the investigation, for a fixed equivalence relation E or type of equivalence relation, which kind of computable quotient presentations are possible with respect to quotients modulo E. We engage with two conjectures that Khoussainov had made and prove various extensions of the Tennenbaum phenomenon to the case of computable quotient presentations of models of arithmetic and set theory. Specifically, no nonstandard model of arithmetic has a computable quotient presentation by a c.e. equivalence relation. No $\Sigma_1$-sound nonstandard model of arithmetic has a computable quotient presentation by a co-c.e. equivalence relation. No nonstandard model of arithmetic in the language $\{+, \cdot, \leq\}$ has a computably enumerable quotient presentation by any equivalence relation of any complexity. No model of ZFC or even much weaker set theories has a computable quotient presentation by any equivalence relation of any complexity. And similarly no nonstandard model of finite set theory has a computable quotient presentation. Concluding from that, we indicate how the program of computable quotient presentations has difficulties with purely relational structures (as opposed to algebras). This is joint work with Joel David Hamkins, GC CUNY. | ||||

Friday Feb 10 2017 | ||||

14:00-15:30 (MS 6221) | Vassilis Gregoriades (U. Turin) | The problem of HYP-isomorphism between recursive Polish spaces | ||

Abstract. It is a fundamental fact of descriptive set theory that every uncountable Polish space is Borel-isomorphic to the Baire space. The effective version of the latter is true as long as the given (recursive) Polish space has no isolated points. Given the importance of this fact in the development of effective descriptive set theory, it is natural to ask if this is also true in general. This however turns out to be false; in fact not only there are recursive uncountable Polish spaces, which are not effectively Borel-isomorphic to the Baire space, but the natural notion of effective Borel reduction carries a rich structure. In this talk we present some central results about these spaces and we describe the main techniques for proving them. | ||||

Friday Jan 27 2017 | ||||

14:00-15:30 (MS 6221) | Zoltán Vidnyánszky (York U. and U. Toronto) | Characterization of order types representable by Baire class 1 functions | ||

Abstract. Let $\mathcal{F}$ be a family of real valued functions on a Polish space $X$. A natural partial ordering on $\mathcal{F}$ is the pointwise ordering, $\leq_p$. The description of linearly ordered subsets of $(\mathcal{F},\leq_p)$ reveals a lot of information about the poset itself. It turns out that the first interesting family of functions to consider is the family of Baire class 1 functions, $\mathcal{B}_1(X)$. Answering a question of Laczkovich, we give a complete combinatorial characterization of the linearly ordered subsets of $(\mathcal{B}_1(X),\leq_p)$. | ||||

Friday Jan 20 2017 | ||||

14:00-15:30 (MS 6221) | Minh Tran (UIUC) | Tame structures via multiplicative character sums over constructible subsets of finite fields | ||

Abstract. We study the model theory of the structure $(\mathbb{F}; <)$ where $\mathbb{F}$ is the algebraic closure of the field of $p$ elements and $<$ is an ordering on $\mathbb{F}^\times$ induced by an injective group homomorphism $\chi: \mathbb{F}^\times \to \mathbb{C}^\times$. Various notions of model theoretic tameness of the structure turn out to be consequences of number theoretic behaviors of the character map $\chi$. The results obtained are attempts to bring number theoretic phenomena of this type into model theory, following a suggestion by van den Dries, Hrushovski and Kowalski. | ||||

Friday Jan 13 2017 | ||||

14:00-15:30 (MS 6221) | Spencer Unger (UCLA) | Borel circle squaring | ||

Abstract. We give a completely constructive solution to Tarski's circle squaring problem.
More generally, we prove a Borel version of a general equidecomposition theorem
due to Laczkovich. This answers a question of Wagon. Our proof
uses ideas from the study of flows in networks, and a recent result of Gao,
Jackson, Khrone, and Seward on special types of witnesses to the
hyperfiniteness of free Borel actions of $\mathbb{Z}^d$. This is joint work
with Andrew Marks. | ||||

Friday Nov 18 2016 | ||||

14:00-15:30 (MS 6221) | Anton Bernshteyn (UIUC) | Measurable graph colorings and the Lovasz Local Lemma | ||

Abstract. The Lovasz Local Lemma, or the LLL for short, is an immensely important tool in probabilistic combinatorics. It is typically used to demonstrate the existence of a function $f \colon X \to Y$ satisfying certain ``local'' combinatorial constraints, where $X$ is an underlying combinatorial structure (e.g. a graph) and $Y$ is a (usually finite) set (e.g. a set of colors). Since its first appearance in 1975, the LLL found numerous applications in combinatorics, some of them straightforward, and some highly technical and sophisticated. In this talk, we will consider the following question: Assume $X$ is equipped with a standard Borel structure and a probability Borel measure $\mu$. Can the function $f$, whose existence is asserted by the LLL, be $\mu$-measurable? Most of our attention will be focused on the situation when the combinatorial structure on $X$ is in some sense ``induced'' by a measure-preserving action of a countable group $\Gamma$. We will see that for some actions the answer is positive (which yields measurable analogs of various combinatorial consequences of the LLL for such actions). On the other hand, for some actions the measurable version of the LLL fails; in fact, if $\Gamma$ is amenable, then a probability measure-preserving action of $\Gamma$ satisfies a measurable analog of the LLL if and only if it has infinite entropy. | ||||

Friday Oct 28 2016 | ||||

15:00-15:50 (MS 6221) | Alessandro Achille (UCLA CS Dept.) | A Vietoris-Smale mapping theorem for the homotopy of hyperdefinable sets | ||

Abstract. Classical results of Vietoris (1927), Begle (1950), Smale (1950) and Dugundji (1969) allow to compare the homotopy of two topological spaces $X$ and $Y$ whenever a map $f : X \rightarrow Y$ with sufficiently trivial fibers is given (acyclic, contractible, etc.).
We apply similar techniques in o-minimal expansions of fields to compare the (o-minimal) homotopy of a definable set $X$ with the homotopy of some of its bounded hyperdefinable quotients $X/E$. As a special case we obtain some homotopy comparison results due to Delfs-Knebush (semialgebraic case) and Baro-Otero and we strengthen previous results on the higher homotopy groups of $G/G^{00}$, where $G$ is a definably compact group and $G^{00}$ is the infinitesimal subgroup. Under suitable assumptions on $E$ we show that $\dim(X) = \dim_R(X/E)$. In particular we obtain a new proof of Pillay's group conjecture $\dim(G) = \dim_R(G/G^{00})$ largely independent of the group structure of $G$. Joint work with Alessandro Berarducci. (Note unusual starting time, 3pm.) | ||||

Friday Oct 14 2016 | ||||

14:00-15:30 (MS 6221) | Ronnie Chen (Caltech) | Structurability by locally finite contractible simplicial complexes | ||

Abstract. By a result of Jackson, Kechris, and Louveau, every treeable compressible countable Borel equivalence relation (CBER) admits a treeing where each vertex has degree at most 3. We generalize this to show that every compressible CBER structurable by $n$-dimensional contractible simplicial complexes is structurable by $n$-dimensional contractible simplicial complexes in which each vertex is contained in at most $c_n$ simplices, where $c_n$ depends only on the dimension $n$. The proof is based on a classical result of Whitehead in algebraic topology. | ||||

Friday Sep 16 2016 | ||||

14:00-15:30 (MS 6221) | Haim Horowitz (Hebrew U) | On the non-existence and definability of mad families | ||

Abstract. By an old result of Mathias, there are no mad families in the Solovay model constructed by the Levy collapse of a Mahlo cardinal. By a recent result of Törnquist, the same is true in the classical model of Solovay as well. In a recent paper, we show that ZF+DC+"there are no mad families" is actually equiconsistent with ZFC. I'll present the ideas behind the proof in the first part of the talk.
In the second part of the talk, I'll discuss the definability of maximal eventually different families and maximal cofinitary groups. In sharp contrast with mad families, it turns out that Borel MED families and MCGs can be constructed in ZF. Finally, I'll present a general problem in Borel combinatorics whose solution should explain the above difference between mad and maximal eventually different families, and I'll show how large cardinals must be involved in such a solution. This is joint work with Saharon Shelah. |