Blog Archives

Topic Archive: Ramsey theory

CUNY Logic WorkshopFriday, December 2, 20162:00 pmGC 6417

Reed Solomon

Weihrauch reducibility and Ramsey theorems

University of Connecticut

Weihrauch reducibility is a common tool in computable analysis for understanding and comparing the computational content of theorems. In recent years, variations of Weihrauch reducibility have been used to study Ramsey type theorems in the context of reverse mathematics where they give a finer analysis than implications in RCA0 and they allow comparisons of computably true principles. In this talk, we will give examples of recent results and techniques in this area.

CUNY Logic WorkshopFriday, December 11, 20152:00 pmGC 6417

Dana Bartosova

Ramsey theory and topological dynamics

Universidade de São Paulo

I will introduce two prominent dynamical systems for a given toplogical group, the greatest ambit and the universal minimal flow, as spaces of (near) ultrafilters on certain Boolean algebras. Representing a topological group as a group of isometries of a highly symmetric structure, I will hint how metrizability and triviality of the universal minimal flow is linked to the (approximate) structural Ramsey property. My focus will lie on problems that arise in the study of universal minimal flows in Ramsey theory, model theory, set theory and continuum theory.

Set theory seminarModels of PAThursday, June 18, 20155:00 pm4214-03Math Thesis room

Mauro Di Nasso

Ultrafilters and nonstandard methods in combinatorics of numbers

Universita di Pisa

In certain areas of Ramsey theory and combinatorics of numbers, diverse non-elementary methods are successfully applied, including ergodic theory, Fourier analysis, (discrete) topological dynamics, algebra in the space of ultrafilters. In this talk I will survey some recent results that have been obtained by using tools from mathematical logic, namely ultrafilters and nonstandard models of the integers.

On the side of Ramsey theory, I will show how the hypernatural numbers of nonstandard analysis can play the role of ultrafilters, and provide a convenient setting for the study of partition regularity problems of diophantine equations. About additive number theory, I will show how the methods of nonstandard analysis can be used to prove density-dependent properties of sets of integers. A recent example is the following theorem: If a set $A$ of natural numbers has positive upper asymptotic density then there exists infinite sets $B$, $C$ such that their sumset $C+B$ is contained in the union of $A$ and a shift of $A$. (This gives a partial answer to an old question by Erdős.)

The slides are here.

Model theory seminarCUNY Logic WorkshopFriday, March 13, 20152:00 pmGC 6417

Sergei Starchenko

Ramsey-type theorems in certain NIP theories

University of Notre Dame

In the paper “Crossing patterns of semi-algebraic sets” (J. Combin. Theory Ser. A 111, 2005) Alon et al. showed that families of graphs with the edge relation given by a semialgebraic relation of bounded complexity satisfy a stronger regularity property than arbitrary graphs. In this talk we show that this can be generalized to families of graphs whose edge relation is uniformly definable in a structure satisfying a certain model theoretic property called distality.

This is a joint work with A. Chernikov.

CUNY Logic WorkshopFriday, November 7, 20142:00 pmGC 6417

Stevo Todorcevic

Choice principles and Ramsey theory

University of Toronto

This talk will provide an overview of results of Ramsey theory that have close relationships with constructions of models of ZF that distinguish between various forms of the Axiom of Choice. Some open problems and directions for further research will also be discussed.

NERDS: New England Recursion & Definability SeminarSaturday, October 18, 20143:20 pmAssumption College, Worcester, MA

Reed Solomon

Ramsey’s Theorem applied to infinite traceable graphs

University of Connecticut

We consider three applications of Ramsey’s Theorem to infinite traceable graphs and finitely generated lattices from the point of view of reverse mathematics. For two of the applications, we will show that Ramsey’s Theorem is necessary while for the third application, it is not necessary. We will conclude with some related open questions.

Set theory seminarFriday, September 5, 201410:00 amGC 6417

Jose Mijares

Local Ramsey theory: an abstract approach

University of Denver

This talk is about an abstract version of the notion of semi-selective co-ideal for subsets of a topological Ramsey space. This version is useful to characterize the corresponding generalization of the local Ramsey property in “topological terms”. We will also talk about forcing notions related to this abstract version of semi-selectivity, generalizing those related to Ellentuck’s space, and we will comment on some applications.

CUNY Logic WorkshopFriday, November 14, 20142:00 pmGC 6417

Algebraic and model-theoretic methods in constraint satisfaction

Université Diderot – Paris 7

The Constraint Satisfaction Problem (CSP) of a first-order structure S in a finite relational language is the problem of deciding whether a given conjunction of atomic formulas in that language is satisfiable in S. Many classical computational problems can be modeled this way. The study of the complexity of CSPs involves an interesting combination of techniques from universal algebra, Ramsey theory, and model theory. I will present an overview over these techniques as well as some wild conjectures.

Set theory seminarFriday, September 12, 201410:00 amGC 5382

Erin Carmody

An alternate proof of the Halpern-Läuchli Theorem in one dimension

The CUNY Graduate Center

I will present a new proof of the strong subtree version of the Halpern-Läuchli Theorem, using an ultrafilter on $\omega$. The one dimensional Halpern-Läuchli Theorem states that for every finite partition of an infinite, finitely branching tree $T$, there is one piece $P$ of the partition and a strong subtree $S$ of $T$ such that $S \subseteq P$. This will cover the one dimensional case, with hopes that the proof can be extended to cover a product of trees.

Chris Conidis
College of Staten Island - CUNY
Prof. Conidis received his Ph.D. in mathematics from the University of Chicago in 2009, under the supervision of Denis Hirschfeldt, Antonio Montalban, and Robert Soare, and subsequently held postdoctoral positions at the University of Waterloo and at Vanderbilt University. His work applies techniques of computability theory to problems in algebra, analysis, and combinatorics. He is now an Assistant Professor at the College of Staten Island in CUNY.
CUNY Logic WorkshopFriday, September 5, 20142:00 pmGC 6417

Jose Mijares

Topological Ramsey spaces and Fraïssé structures

University of Denver

There seems to be a natural relationship between topological Ramsey spaces and Fraïssé classes of finite structures. In fact, for some Fraïssé classes satisfying the Ramsey property, it is possible to define a topological Ramsey space such that the Fraïssé limit of the class is essentially an element of the space. We will talk about examples of this phenomenon, describe the general case to some extent, and comment about how this could be understood as a abstract tool to classify Fraïssé structures.

Jose Mijares
University of Denver
Goyo Mijares received his Ph.D. in 2007 from the Central University of Venezuela, and is now a postdoctoral scholar at the University of Denver. He studies set theory, Ramsey theory, topological dynamics, combinatorics, and functional analysis.
CUNY Logic WorkshopFriday, February 7, 20142:00 pmGC 6417

Damir Dzhafarov

New directions in reverse mathematics

University of Connecticut

Mathematics today benefits from having “firm foundations,” by which we usually mean a system of axioms sufficient to prove the theorems we care about. But given a particular theorem, can we specify precisely which axioms are needed to derive it? This is a natural question, and also an ancient one: over 2000 years ago, the Greek mathematicians were asking it about Euclid’s geometry. Reverse mathematics provides a modern approach to this kind of question. A striking fact repeatedly demonstrated in this area is that the vast majority of mathematical propositions can be classified into just five main types, according to which set-existence axioms are needed to carry out their proofs. But more recently, a growing number of principles falling outside this classification have emerged, whose logical strength is more difficult to understand. These turn out to include many important mathematical results, such as various combinatorial problems related to Ramsey’s theorem, and several set-theoretic equivalents of the axiom of choice. I will discuss some of these “irregular” principles, and some new approaches that have arisen from trying to understand why their strength is so different from that of most other theorems. In particular, this investigation reveals new connections between different mathematical areas, and exposes the rich and complex combinatorial and algorithmic structure underlying mathematics as a whole.

Model theory seminarFriday, October 18, 201312:30 pmGC6417

Lynn Scow

Ramsey Transfer Theorems

Vassar College

We survey some of the known approaches to transfer a Ramsey theorem for one class of finite structures to another. We will isolate some easy consequences and point to further directions.

Set theory seminarFriday, October 18, 20139:30 amGC 6417Two talks for set theory seminar on this day

Marcin Sabok

Canonical Ramsey theory on Polish spaces

Instytut Matematyczny Uniwersytetu Wrocławskiego, Instytut Matematyczny Polskiej Akademii Nauk

I would like to give an overview of recent results in canonical Ramsey theory in the context of descriptive set theory. This is the subject of a recent monograph joint with with Vladimir Kanovei and Jindra Zapletal. The main question we address is the following. Given an analytic equivalence relation on a Polish space, can one find a large subset of the space on which it has a simple form? Canonical Ramsey theory stems from finite combinatorics and is concerned with finding canonical forms of equivalence relations on finite (or countable) sets. We obtain canonization results for analytic and Borel equivalence relations and in cases when canonization is impossible, we prove ergodicity theorems. For a publisher’s book description see:

Natasha Dobrinen
University of Denver
Professor Dobrinen earned her Ph.D. at the University of Minnesota under Karel Prikry in 1996, afterwards holding post-doctoral positions at Penn State and the University of Vienna before moving to the University of Denver. Her research interests mainly fall under the broad category of logic and foundations of Mathematics, and includes research in set theory, Ramsey theory, Boolean algebras, and measure theory. She has investigated relationships between random reals, eventually dominating functions, measure, generalized weak distributive laws, infinitary two-player games, and complete embeddings of the Cohen algebra into complete Boolean algebras. Currently, she is working on problems in Ramsey theory, problems regarding the structure of the Tukey types of ultrafilters, and problems involving both.
Diana Ojeda Aristizabal
Cornell University
Diana Ojeda Aristizabal is a Ph.D. candidate in mathematics at Cornell University, working with Justin Moore in the area of Ramsey theory and geometry of Banach spaces.