Ideals and determinacy (Cont.)

Speaker: 

Nam Trang

Institution: 

University of North Texas

Time: 

Monday, January 25, 2021 - 4:00pm to 5:30pm

Location: 

Zoom

We present some ideas involved in the proof of the equiconsistency
of AD_\reals + Theta is regular and the existence of a strong,
pseudo-homogeneous ideal on P_{\omega_1}(\reals). Some variations of this
hypothesis are also shown to be equiconsistent with AD_\reals + Theta is
regular. This work is related to and partially answers a long-standing
conjecture of Woodin regarding the equiconsistency of AD_\reals + Theta is
regular and CH + the nonstationary ideal on \omega_1 is \omega_1-dense. We
put this result in a broader context of the general program of understanding
connections between canonical models of large cardinals, models of
determinacy, and strong forcing axioms (e.g. PFA, MM). This is joint work with G. Sargsyan and T. Wilson.

Kurepa trees and almost disjoint families under determinacy

Speaker: 

Nam Trang

Institution: 

UN Texas

Time: 

Monday, March 9, 2020 - 4:00pm to 5:30pm

Location: 

RH 440R

We formulate the Kurepa hypothesis (KH) and its generalizations in determinacy and prove KH fails there. More generally, we show that if $\kappa < \Theta$ and $cof(\kappa) > \omega$, then the set of branches through a  $\kappa$-tree must be well-orderable and has cardinality less than or equal to \kappa. We also show there are no maximal almost disjoint families at $\omega_1$ and its appropriate generalizations at regular cardinals $\kappa < \Theta$. This is joint work with William Chan and Steve Jackson.

What you can define from a Cantor Set

Speaker: 

Erik Walsber

Institution: 

UCI

Time: 

Monday, March 2, 2020 - 4:00pm to 4:50pm

Location: 

RH 440R

This talk concerns a connection between fractals and an interesting tame structure. If K is a Cantor subset of the real line (compact nowhere dense perfect subset) then (R,<,+,K) defines an isomorphic copy of the monadic second order theory of the successor function. This result is sharp as the monadic second order theory of the successor defines an isomorphic copy of (R,<,+,C) where C is the classical middle-thirds Cantor set. One can also show that if X is essentially any fractal subset of Euclidean space then (R,<,+,X) defines a Cantor subset of the real line, but I probably won't have time to say much about this. Joint work with Philipp Hieronymi.

Connected Component in n-dependent groups

Speaker: 

Nadja Hempel

Institution: 

UCLA

Time: 

Monday, February 24, 2020 - 4:00pm to 5:30pm

Location: 

RH 440R

1-dependent theories better known as 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. Recently, in a joint work with Chernikov, we proved the existence of strictly n-dependent groups for all natural numbers n and we started studying their properties. The connected component over A, inspired by the definition of the connected component of algebraic group, is the intersection of all A-type definable subgroups of bounded index. A crucial fact about (type)definable groups in 1-dependent theories is the absoluteness of their connected components: Namely given a definable group G and a small set of parameters A, we have that the connected component of G over A coincides with the one over the empty set. A
 
We will give examples of n-dependent groups and discuss a generalization of absoluteness of the connected component to n-dependent theories.

 

From Finite to Infinite Combinatorics (Continued)

Speaker: 

Asaf Ferber

Institution: 

UC Irvine

Time: 

Monday, February 10, 2020 - 4:00pm to 5:30pm
<p>In this talk we will sketch some combinatorial statements which are quite trivial in the finite case and discuss their infinite analogs, which are quite often way harder (or mabye even false...). After giving some interesting examples in various subareas, we will turn our focus into one specific open problem which is known as the ``unfriendly partition conjecture''. More specifically, given a graph $G=(V,E)$, a partition $V=V_0\cup V_1$ is said to be ``unfriendly'' if every vertex $v\in V_i$ has at least as many neighbors in $V_{i+1}$ rather in $V_i$ (the computation $i+1$ is done mod 2). The statement ``every finite graph has an unfriendly partition'' is trivial. We will see that for the infinite case, this statement can be wrong as was shown by Shelah and Milner, and basically the only unknown case is when $G$ is a graph of an infinite but countable size.</p>

<p>The talk is based on few papers by other researchers (among other: a paper by Soukup, the Shelah-Milner paper, a paper by Thomassen, and more).</p>

 

From finite to infinite combinatorics

Speaker: 

Asaf Ferber

Institution: 

UC Irvine

Time: 

Monday, February 3, 2020 - 4:00pm to 5:30pm

Location: 

RH 440R

In this talk we will sketch some combinatorial statements which are quite trivial in the finite case and discuss their infinite analogs, which are quite often way harder (or mabye even false...). After giving some interesting examples in various subareas, we will turn our focus into one specific open problem which is known as the ``unfriendly partition conjecture''. More specifically, given a graph $G=(V,E)$, a partition $V=V_0\cup V_1$ is said to be ``unfriendly'' if every vertex $v\in V_i$ has at least as many neighbors in $V_{i+1}$ rather in $V_i$ (the computation $i+1$ is done mod 2). The statement ``every finite graph has an unfriendly partition'' is trivial. We will see that for the infinite case, this statement can be wrong as was shown by Shelah and Milner, and basically the only unknown case is when $G$ is a graph of an infinite but countable size.

The talk is based on few papers by other researchers (among other: a paper by Soukup, the Shelah-Milner paper, a paper by Thomassen, and more).

On a semilinear Zarankiewicz problem

Speaker: 

Minh Chieu Tran

Institution: 

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

Speaker: 

Artem Chernikov

Institution: 

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

Speaker: 

Erik Walsberg

Institution: 

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.

Speaker: 

Erik Walsberg

Institution: 

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.

 

Pages

Subscribe to RSS - Logic Set Theory