Archives of: Carnegie Mellon Logic Seminar

Natasha Dobrinen: The big Ramsey degrees for the universal triangle-free graph

Mathematical logic seminar – Jun 5 2017
Time:     3:00pm – 4:00 pm

Room:     Wean Hall 8220

Speaker:         Natasha Dobrinen
Department of Mathematics
University of Denver

Title:     The big Ramsey degrees for the universal triangle-free graph

Abstract:

The Rado graph (aka the countable random graph) is the unique countable graph G which is:

a) Universal, that is G contains an induced copy of every finite graph.

b) Homogeneous, that is any isomorphism between finite induced subgraphs
of G extends to an automorphism of G.

The construction of the Rado graph works with many classes of finite structures (the Fraïssé classes), assigning to each Fraïssé class a countable, universal and homogeneous structure called the Fraïssé limit.

Ramsey theory on relational structures can be studied from two vantage points. The first, more classical, is to study when, given two finite structures A and B and given any k greater than 1, there is another finite structure C such that for any coloring of all copies of A in C into k colors, there is a copy of B in C in which all copies of A have the same color. A Fraïssé class of finite relational structures has the Ramsey property if this holds for any two structures A and B in the class. Nešetřil and Rödl have shown that many classes of finite ordered relational structures have the Ramsey property, including finite ordered graphs and finite ordered triangle-free graphs.

The second, and of much recent interest, is to study colorings of copies of a finite structure inside an infinite homogenous structure, usually the Fraïssé limit of some Fraïssé class of finite structures. It has been shown that any finite coloring of the vertices of the Rado graph can be reduced to one color on a subgraph which is also a Rado graph. For edges and other structures with more than one vertex, Sauer has proved this to be impossible. However, he also proved that given a finite graph A, there is a number n(A) such that any coloring of all copies of A in the Rado graph into finitely many colors may be reduced to n(A) colors on a copy of the Rado graph. We say, then, that the Rado graph has finite big Ramsey degrees. Similar results have been obtained for other countable homogeneous structures, though many are still open.

We have looked at the problem of finite big Ramsey degrees for the universal triangle-free graph H, that is, the homogeneous graph with no triangles into which every countable triangle-free graph embeds. This is the first homogeneous structure omitting a subtype to be addressed for big Ramsey degrees. Using the method of forcing, but in ZFC, we prove a new Ramsey theorem on trees which code H, and apply it to deduce that H has finite big Ramsey degrees.

James Cummings: Definable subsets of singular cardinals

Mathematical logic seminar – Apr 11 2017
Time:     3:30pm – 4:30 pm

Room:     Wean Hall 8220

Speaker:         James Cummings
Department of Mathematical Sciences
CMU

Title:     Definable subsets of singular cardinals

Abstract:

Shelah proved the surprising result that if μ is a singular strong limit cardinal of uncountable cofinality, then there is a subset X of μ such that all subsets of μ are ordinal-definable from X. We will give a proof and discuss some complementary consistency results.

Jing Zhang: A polarized partition theorem for large saturated linear orders

Mathematical logic seminar – Mar 28 2017
Time:     3:30pm – 4:30 pm

Room:     Wean Hall 8220

Speaker:         Jing Zhang
Department of Mathematical Sciences
CMU

Title:     A polarized partition theorem for large saturated linear orders

Abstract:     Laver proved the following polarized partition theorem for rational numbers: for any natural number d, any finite coloring f of Q^d, there exist subsets of Q, X_i for i < d, each of which has the same order type as Q such that the product X_1 x … x X_{d-1} gets at most d! many colors. A natural question to ask is what happens when we consider larger saturated linear orders. We will discuss the consistency at the level of strongly inaccessible cardinals that satisfy some indestructibility property. The development of versions of the Halpern-Läuchli theorem at a large cardinal will be pivotal in the proof.

Dana Bartošová: Freedom of action in combinatorial terms

Mathematical logic seminar – Mar 21 2017
Time:     3:30pm – 4:30 pm

Room:     Wean Hall 8220

Speaker:         Dana Bartošová
Department of Mathematical Sciences
CMU

Title:     Freedom of action in combinatorial terms

Abstract:

A group acts freely on a compact Hausdorff space if all of its non-identity elements act without fixed points. By Veech’s theorem, every locally compact topological group admits a free action and the question arises to which other groups this property can be extended. On the other hand, elements of extremely amenable groups act with fixed points under any action but the opposite implication does not hold. We show a combinatorial reformulation of this property and ask how far it is from extreme amenability.

Rick Statman: Backus FP is Turing complete

Mathematical logic seminar – Feb 28 2017
Time:     3:30pm – 4:30 pm

Room:     Wean Hall 8220

Speaker:         Rick Statman
Department of Mathematical Sciences
CMU

Title:     Backus FP is Turing complete

Abstract:

Cartesian monoids are rather simple algebraic structures of which you know many examples. They also travel under many assumed names such as Cantor algebras, Jonsson-Tarski algebras, and Freyd-Heller monoids. John Backus’s FP is just the theory of Cartesian monoids together with fixed points for all Cartesian monoid polynomials.

In his 1977 Turing Award address, John Backus introduced the model of functional programming called “FP”. FP is a descendant of the Herbrand-Godel notion of recursive definablity and the ancestor of the programming language Haskell. One reason that FP is attractive is that it provides “an algebra of functional programs”. However, Backus did not believe that basic FP was powerful enough;

“FP systems have a number of limitations….. If the set of primitive functions and functional forms is weak, it may not be able to express every computable function”. John Backus, 1977 ACM Turing award lecture.

and he moved on to stronger systems. It turns out that, in this respect, Backus was mistaken. Here we shall show that FP can compute every partial recursive function.

Deirdre Haskell: Using model theory to find upper bounds on VC density

Mathematical logic seminar – Feb 21 2017
Time:     3:30pm – 4:30 pm

Room:     Wean Hall 8220

Speaker:         Deirdre Haskell
Department of Mathematics and Statistics
McMaster University

Title:     Using model theory to find upper bounds on VC density

Abstract:

The VC dimension of a collection of sets is a concept used in probability and learning theory. It is closely related to the model-theoretic concept of the independence property. In this talk, I will illustrate these concepts in various examples, and show how the model-theoretic approach can give some bounds on VC density.

Andy Zucker: An ultrafilter proof of the 2-dimensional Halpern-Laüchli Theorem

Mathematical logic seminar – Jan 31 2017
Time:     3:30pm – 4:30 pm

Room:     Wean Hall 8220

Speaker:         Andy Zucker
Department of Mathematical Sciences
CMU

Title:     An ultrafilter proof of the 2-dimensional Halpern-Laüchli Theorem

Abstract:

We will discuss the Halpern-Laüchli Theorem and provide a new proof in dimension 2. The idea is to use an ultrafilter on ω to turn combinatorics on trees into combinatorics on the branches, that is Cantor space. Time permitting, we will discuss obstacles to generalizing the proof to higher dimensions.

James Cummings: Universal graphs

Mathematical logic seminar – Jan 24 2017
Time:     3:30pm – 4:30 pm

Room:     Wean Hall 8220

Speaker:         James Cummings
Department of Mathematical Sciences
CMU

Title:     Universal graphs

Abstract:

The well-known “random countable graph” or “Rado graph” is a countable graph which contains induced copies of every countable graph. We discuss the existence of such objects in uncountable cardinalities.

Andy Zucker: Ramsey degrees big and small II

Mathematical logic seminar – November 29 2016
Time:     3:30pm – 4:30 pm

Room:     Wean Hall 8220

Speaker:         Andy Zucker
Department of Mathematical Sciences
CMU

Title:     Ramsey degrees big and small II

Abstract:

We will consider various aspects of structural Ramsey theory in a countable first-order structure, leading to an investigation of several notions of largeness. For ultrahomogeneous (i.e. Fraisse) structures, the Ramsey theoretic properties of the structure and the dynamical properties of the automorphism group are closely related. This talk should serve as an introduction to the Kechris-Pestov-Todorčević correspondence while also discussing directions for new research.

Andy Zucker : Ramsey degrees big and small

Mathematical logic seminar – November 15 2016
Time:     3:30pm – 4:30 pm

Room:     Wean Hall 8220

Speaker:         Andy Zucker
Department of Mathematical Sciences
CMU

Title:     Ramsey degrees big and small

Abstract:

We will consider various aspects of structural Ramsey theory in a countable first-order structure, leading to an investigation of several notions of largeness. For ultrahomogeneous (i.e. Fraisse) structures, the Ramsey theoretic properties of the structure and the dynamical properties of the automorphism group are closely related. This talk should serve as an introduction to the Kechris-Pestov-Todorčević correspondence while also discussing directions for new research.