Topic Archive: Ramsey theory
Weihrauch reducibility and Ramsey theorems
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.
Ramsey theory and topological dynamics
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.
Ultrafilters and nonstandard methods in combinatorics of numbers
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.
Ramsey-type theorems in certain NIP theories
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.
Choice principles and Ramsey theory
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.
Ramsey’s Theorem applied to infinite traceable graphs
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.
Local Ramsey theory: an abstract approach
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.
Algebraic and model-theoretic methods in constraint satisfaction
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.
An alternate proof of the Halpern-Läuchli Theorem in one dimension
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.
Topological Ramsey spaces and Fraïssé structures
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.
New directions in reverse mathematics
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.
Ramsey Transfer Theorems
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.
Canonical Ramsey theory on Polish spaces
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: