# On a semilinear Zarankiewicz problem

Minh Chieu Tran

Notre Dame

## Time:

Monday, January 6, 2020 - 4:00pm to 5:00pm

Given a set $P$ of $n$ points on the $xy$-plane and a set $R$ of $n$ solid rectangles with edges parallel to the axes, and assuming that no two points  in $P$ lie in two rectangles in $R$, what is the maximum size of the set $I = \{ (p, r) \in P \times R : p \in r\}$ of incidences between $P$ and $R$? For the related problem where $R$ is replaced by a set $L$ of $n$ lines in the planes, the Szemerédi–Trotter Theorem gives us an upper bound $Cn^{4/3}$ for the  size of the set of incidences between $P$ and $L$ where $C$ is a constant (independent of n). Moreover, there are examples showing that the exponent $4/3$ is optimal here. A result by  Jacob Fox, Janos Pach, Adam Sheffer, and Andrew Suk yields the corresponding upper bound  $|I| < Cn^{12/7+ 1/10000}$  with $C$  a constant. However,  using an idea from logic (namely, induction on the complexity of formulas), we can significantly improve this bound to

$$|I| < Cn (\ln n)^3 \quad \text{ with } C \text{ a constant}.$$

We also provide for every fixed constant $C$ and arbitrarily large $n$ an example where $|I| > C n (\ln n)^{1/2}$. The difference between the point-rectangle incidence problem and the point-line incidence problem hints at the modular/ non-modular dividing line in model theory: the incidence relation in the former case is semilinear (i.e., definable in the real ordered additive group), while the incidence in the latter case is semialgebraic (i.e., definable in the real ordered field) but not semilinear.  (Joint with Abdul Basit, Artem Chernikov, Sergei Starchenko, and Terence Tao)

# Regularity Lemma for Hypergraphs with Forbidden Patterns

Artem Chernikov

UCLA

## Time:

Monday, November 4, 2019 - 4:00pm

## Location:

RH 440R

Fix an arbitrary bipartite finite graph H, and let's consider the family of all finite graphs not containing H as an induced subgraph. Recently a strong form of Szemeredi's regularity lemma for such families was established by Lovasz and Szegedy. In particular, up to an arbitrary small error, such graphs can be uniformly approximated by direct products of unary relations. Using a combination of analytic, combinatorial and model-theoretic methods, we establish a generalization of this result for hypergraphs, showing that k-ary hypergraphs omitting a fixed k-partite hypergraph can be uniformly approximated by relations of arity smaller than k. No prior knowledge of the aforementioned notions will be assumed. Joint work with Henry Towsner.

# Model companions of unions of model complete theories

Erik Walsberg

UCI

## Time:

Monday, October 28, 2019 - 4:00pm

## Location:

RH 440R

Suppose $I$ is an index set, $(L_i)_{i \in I}$ is a family of first order languages, and $L_\cap$ is a first order language such that $L_i\cap L_j = L_\cap$ for all distinct $i,j \in I$. Suppose $T_i$ is acomplete, consistent, model complete $L_i$-theory for all $i \in I$ and suppose $T_\cap$ is an $L_\cap$-theory such that $T_i \cap T_j = T_\cap$ for all distinct $i,j \in I$. Let $T_\cup = \bigcup_{i \in I} T_i$. We discuss the question: When does $T_\cup$ have a model companion? Time permitting we will also discuss a number of motivating examples. Joint work with Minh Chieu Tran and Alex Kruckman.

# Model companions of unions of model complete theories.

Erik Walsberg

UCI

## Time:

Monday, October 7, 2019 - 4:00pm to 5:50pm

## Location:

RH 440R

Suppose $I$ is an index set, $(L_i)_{i \in I}$ is a family of first order languages, and $L_\cap$ is a first order language such that $L_i\cap L_j = L_\cap$ for all distinct $i,j \in I$. Suppose $T_i$ is acomplete, consistent, model complete $L_i$-theory for all $i \in I$ and suppose $T_\cap$ is an $L_\cap$-theory such that $T_i \cap T_j = T_\cap$ for all distinct $i,j \in I$. Let $T_\cup = \bigcup_{i \in I} T_i$. We discuss the question: When does $T_\cup$ have a model companion? Time permitting we will also discuss a number of motivating examples. Joint work with Minh Chieu Tran and Alex Kruckman.

# The strength of Sealing

Nam Trang

## Institution:

University of North Texas, Denton

## Time:

Monday, May 20, 2019 - 4:00pm to 5:30pm

## Location:

RH440R

Sealing is a type of generic absoluteness condition introduced by Woodin that asserts in strong terms that the theory of the universally Baire sets cannot be changed by forcing. generic-LSA is the statement that the Largest Suslin Axiom (LSA) holds in all generic extensions. Under a mild large cardinal hypothesis, we show that Sealing is equiconsistent with generic-LSA. As a consequence, Sealing is weaker than the theory ZFC+there is a Woodin cardinal which is a limit of Woodin cardinals". Sealing's consistency being weak represents an obstruction to the current program of descriptive inner model theory. Going beyond this bound in core model induction applications seems challenging and requires us to construct third order objects (subsets of the universally Baire sets). We will state the precise theorems and discuss their impact on current developments of inner model theory. Time allowed, we will talk a bit about how to overcome the the obstructions imposed by Sealing. This is joint work with G. Sargsyan.

# Mixing times and Hitting times for general Markov processes using Nonstandard Analysis

Kevin Duanmu

UC Berkeley

## Time:

Monday, October 14, 2019 - 4:00pm

## Location:

TBA

Nonstandard analysis, a powerful machinery derived from mathematical logic, has had many applications in probability theory as well as stochastic processes. Nonstandard analysis allows construction of a single object---a hyperfinite probability space---which satisfies all the first order logical properties of a finite probability space, but which can be simultaneously viewed as a measure-theoretical probability space via the Loeb construction. As a consequence, the hyperfinite/measure duality has proven to be particularly in porting discrete results into their continuous settings.

In this talk, for every general-state-space discrete-time Markov process satisfying appropriate conditions, we construct a hyperfinite Markov process which has all the basic order logical properties of a finite Markov process to represent it.  We show that the mixing time and the hitting time agree with each other up to some multiplicative constants for discrete-time general-state-space reversible Markov processes satisfying certain condition. Finally, we show that our result is applicable to a large class of Gibbs samplers and Metropolis-Hasting algorithms.

# Precipitous Ideals III

## Speaker:

Matthew D. Foreman

UCI

## Time:

Monday, March 11, 2019 - 4:00pm to 5:30pm

## Location:

RH 440R

This lecture will complete the presentation of a new result answering a question of Welch about precipitous ideals on weakly compact cardinals.

# Precipitous Ideals II

## Speaker:

Matthew D. Foreman

UCI

## Time:

Monday, March 4, 2019 - 4:00pm to 5:30pm

## Location:

RH 440R

This lecture will present a new result answering a question of Welch about precipitous ideals on weakly compact cardinals.

# Precipitous Ideals I

## Speaker:

Matthew D. Foreman

UCI

## Time:

Monday, February 25, 2019 - 4:00pm to 5:30pm

## Location:

RH 440R

This lecture will review the definitions and basic facts about precipitous ideals and generic elementary embeddings.

# Omitting types in the logic of metric structures (Joint work with I. Farah)

Menachem Magidor

## Institution:

Einstein Institute of Mathematics

## Time:

Monday, February 4, 2019 - 4:00pm to 5:00pm

## Location:

440R RH

The logic of metric structures was introduced by Ben Yaacov, Berenstein , Henson and Usvyatsov. It is a version of continuous logic which allows fruitful model theory for  many kinds of metric structures .There are many aspects of   this logic which make it similar to  first order logic, like compactness, a complete proof system, an omitting types theorem for complete  types  etc. But when one tries to generalize the omitting type criteria to general (non-complete) types the problem turns out to be essentially more difficult than the first order situation.For instance one can have two types (in a complete theory) that each one can be omitted , but they can not be omitted simultaneously.