Schedule for: 18w5180 - Unifying Themes in Ramsey Theory

A buffet dinner is served daily between 5:30pm and 7:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.

A brief introduction to BIRS with important logistical information, technology instruction, and opportunity for participants to ask questions.

Ramsey theory is a natural perspective to use when studying the structure of large data sets. Big data, machine learning, and neural nets can all be profitably seen through this lens. We follow up on recent work of Calude and Longo ("The Deluge of Spurious Correlations in Big Data") by providing meaningful interpretations of basic Ramsey results in the setting of statistics. Our first example will be to interpret Goodman's Theorem in this context. In this talk I will lay out some of the current research in the area, present open problems relevant to researchers in Ramsey theory, and advertise some soon to be published work in these fields. Hopefully this will spur even more sophisticated connections of Ramsey theory with big data.
This contains joint work with Michael Waddell, Columbia University.

A large portion of the known Ramsey classes are essentially classes of ordered binary symmetric structures, for example the $K_n$-free graphs, Sauer's $S$-metric spaces, Cherlin's metrically homogeneous graphs, Braunfeld's $\Lambda$-ultrametric spaces or Conant's generalized metric spaces. All of these can be shown to be Ramsey using the Hubicka--Nesetril Theorem and some variant of the shortest path completion. We study the limits of the shortest path completion and introduce the semigroup-valued metric spaces --- a general framework which includes all the aforementioned classes. We find their Ramsey expansions and prove EPPA. We also conjecture that every primitive strong amalgamation class in a finite binary symmetric language can be understood as a semigroup-valued metric space.
This is joint work with Hubicka and Nesetril

Meet in foyer of TCPL to participate in the BIRS group photo. The photograph will be taken outdoors, so dress appropriately for the weather. Please don't be late, or you might not be in the official group photo!

Lunch is served daily between 11:30am and 1:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

We use techniques of logic, particularly set theory, to determine upper bounds on the big Ramsey degrees of the universal homogeneous k-clique-free graphs, for each k greater than two.

It is an open problem whether the Hrushovski extension property holds for tournaments. It is equivalent to a problem concerning a profinite topology and a characterization of closed f.g. subgroups in this topology. During the talk I will discuss a generalization of the latter problem to a family of profinite topologies.

Meet in the Corbett Hall Lounge for a guided tour of The Banff Centre campus.

A buffet dinner is served daily between 5:30pm and 7:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

The work of Kechris, Pestov and Todorcevic has revealed a close connection between Ramsey theory of model-theoretic structures and topological dynamics of their automorphism groups, providing a rich source of examples of extremely amenable topological groups. Next to Ramsey theory, there is a second pathway to extreme amenability of topological groups: the phenomenon of measure concentration, which was exhibited in the 1970s by Milman (extending an idea going back to the work of Levy) and linked with extreme amenability in Milman's groundbreaking joint work with Gromov. In the late 1990s, Gromov offered a far-reaching generalization of the measure concentration phenomenon: the concentration topology on the space of metric measure spaces. Inspired by the striking applications of measure concentration in topological dynamics, Pestov suggested to study manifestations of Gromov's concentration to non-trivial spaces in the context of transformation groups. In the talk I will report on recent progress in that direction, focusing on automorphism groups of metric model-theoretic structures and connections with Ramsey theory.
Whereas for discrete structures dissipation and reasons related to ergodic theory prevent any kind of concentration, the situation is quite different in the continuous case.

A Polish group G is said to be uniquely ergodic when every minimal G-flow admits a unique invariant probability measure. For various examples of amenable automorphism groups of Fraïssé structures, it has been shown that this property holds. I will prove that this is also true in the only remaining case in Cherlin's classification for directed graphs: the semigeneric directed graph.
This work follows from the papers of Angel-Kechris-Lyons and Pawliuk-Sokic, however it uses a new method not relying on the probabilistic method. If I have time, I would also like to discuss the fact that the class of uniquely ergodic groups is closed under extension.

We show that for Polish groups, the property of having metrizable universal minimal flow is preserved under group extensions; if G is Polish, H is a closed normal subgroup of G, and both M(H) and M(G/H) are metrizable, then M(G) is metrizable. In the case that G is non-Archimedean, this theorem has consequences in structural Ramsey theory for which we do not know a combinatorial proof.
This is joint work with Colin Jahel.

A model M of a fixed first-order language is called homogeneous if every isomorphism between its finitely generated submodels extends to an automorphism of M. Theory of homogeneous models was developed by Fraisse (1954) and now belongs to the folklore of model theory. We shall discuss a stronger version of homogeneity, where extending partial isomorphisms is functorial, in the sense that it preserves compositions. We call it ``uniform homogeneity". This property implies that the automorphism group of M contains isomorphic copies of all automorphism groups of its finitely generated submodels. It turns out that most of the well known countable homogeneous models are uniformly homogeneous, which is implied by the existence of so-called Katetov functor, studied recently by Masulovic and the author. Nevertheless, there exist finite homogeneous models that are not uniformly homogeneous. We shall present an example of such a model which has 6 elements. It is not clear whether there exists a smaller model with this property. We shall also present countable infinite homogeneous models that are far from being uniformly homogeneous. One of the examples has the property that its automorphism group is torsion-free, while among the automorphism groups of its finite submodels one can find arbitrarily large finite products of finite cyclic groups.
The talk is based on two works, one joint with S. Shelah, another one joint with B. Kuzeljevic.

A complete first order theory of a relational signature is called monomorphic iff all its models are monomorphic (i.e. have all the n-element substructures isomorphic, for each positive integer n). We show that a complete theory T having infinite models is monomorphic iff it has a countable monomorphic model and confirm the Vaught conjecture for monomorphic theories.

This talk provides a story of equality of homomorphism-homogeneous classes. Cameron and Nesetril [1] suggested a novel notion of homomorphism-homogeneity for relational structure that requires every local homomorphism between finite induced substructures extends to homomorphism to the whole structure extending thus a classical notion of ultrahomogeneity in sense of Fraisse. Depending on types of local homomorphism as well as the extending one it is possible to define various types of homomorphism-homogeneity, e.g. monomorphism-homogeneity extending local monomorphism to homomorphism. Mentioned work was an onset of wide classification program attempting to describe corresponding homogeneity classes. Already in this work there was a question about equality of classes HH and MH which was answered by Rusinov and Schweitzer 4 years later for countable undirected grahs. Later, with Hubicka and Masulovic [3] we studied L-colored graphs, graphs having their edges as well as vertices colored by partial ordered set L, and showed conditions under which classes HH and MH are equal for finite L-colored graphs. We extend this result by considering countably infinite P,Q-colored graphs, graphs coloring vertices and edges by two different partially ordered sets P and Q, and showed that necessary as well as suffcient condition for equality of classes MH and HH is that Q is a linear order [4].
Joint work with Andres Aranda.
[1] P. J. Cameron, J. Nesetril (2006), Homomorphism-homogeneous relational structures, Combinatorics, probability and computing 15(1-2): 91{103.
[2] M. Rusinov, P. Schweitzer (2010), Homomorphismhomogeneous graphs, Journal of Graph Theory 65(3):253{262.
[3] D. Hartman, J. Hubicka, D. Masulovic (2014) Homomorphism-homogeneous L-colored graphs, European Journal of Combinatorics 35: 313{32.
[4] A. Aranda, D. Hartman (2018), Morphism extension classes of countable L-colored graphs. Preprint at arXiv:1805.01781.

In this non structured session, everyone will be invited to propose and discuss any open problems they may have.

An edge-ordered graph is a graph with linearly ordered set of edges. We introduce and study Ramsey numbers of edge-ordered graphs, called edge-ordered Ramsey numbers. We prove some basic properties of these numbers for general edge-ordered graphs and we provide some stronger estimates for special classes of edge-ordered graphs. We also pose some new open problems and compare edge-ordered Ramsey numbers with the standard Ramsey numbers of graphs and with ordered Ramsey numbers, which are Ramsey numbers for graphs with linearly ordered vertex sets.
Joint work with Mate Vizer

One of the numerous strengthenings of Ramsey's theorem is due to Erdös and Rado, who analyzed what partition properties can be obtained on m-subsets of the naturals when colourings are not necessarily finite. Large monochromatic sets may not appear in that case, but there is a finite list of behaviors, called "canonical", to which every coloring reduces. The purpose of this talk will be to remind certain not so well-known analogous theorems of the same flavor that were obtained by Prömel in the eighties for various classes of structures (like graphs, hypergraphs, or Boolean algebras), and to show that such theorems can in fact be deduced in the more general setting of Fraïssé classes.

We will discuss the classification of homogeneous finite-dimensional permutation structures, i.e. structures in a language of finitely many linear orders, recently completed in joint work with Pierre Simon. After constructing the catalog of such structures, we will present some of the key concepts in the classification, primarily coming from Simon's work on linear orders in omega-categorical structures. We will also touch on the Ramsey property for these structures, which may be viewed as Ramsey expansions of certain metric-type structures.
Joint work with Pierre Simon

Option 1:
Hike from BIRS to Sundance Canyon and back for dinner
http://hikingwithbarry.com/2010/04/30/sundance-canyon-%E2%80%93-banff-national-park-%E2%80%93-hike-alberta
Option 2:
Spend afternoon at Lake Louise, hike around the lake, lookout, scotch in Lakeview Lounge, shopping, ..
There would be a transportation cost and we may not be back at BIRS for dinner so may have to eat in Banff town at our own expense.
http://hikingwithbarry.com/2013/03/29/lakeshore-trail-lake-louise-hiking-alberta

I will present an ultrafilter proof of the infinitary version of the Gowers theorem for multiple tetris operations. Bartosova and Kwiatkowska previously gave a constructive proof of the corresponding finitary version, which has applications to the dynamics of the Lelek fan.

In [4] the authors used the Local Ramsey theory to prove that a countable Frechet group is metrizable if, and only if, its topology is analytic. We use this result together with the connections between the Tukey ordering and topology found in [2] to give a characterization of separable metrizable groups. We prove that a separable group is metrizable if, and only if, it is Frechet and the the ideal of converging sequences to the identity is Tukey below some basic order that is analytic. Results in this direction have been obtained before in [1].
[1] S. Gabriyelyan, J. Kakol and A. Leiderman. On topological groups with a small base and metrizability. Fundamenta Mathematicae, 229 (2015) 129-157.
[2] S. Solecki and S. Todorcevic. Cofinal types of topological directed orders. Ann. Inst. Fourier, Grenoble, 54, 6 (2004), 1877-1911.
[3] S. Todorcevic. Introduction to Ramsey spaces. Annals of Mathematics Studies, No 174, Princeton, 2010.
[4] S. Todorcevic and C. Uzcategui. Analytic $k$-spaces. Topology and its applications, 146-147 (2005) 511-526. \end{thebibliography}

A special case of the Halpern--Lauchli theorem implies that for a given 2-coloring of a perfect binary tree there exist a perfect subtree and an infinite set A of levels such that the coloring is monochromatic on nodes of the subtree coming from levels in A. We say that a collection of infinite sets R is (HL) if the statement can be strengthened by requiring that the set of levels A is in R instead of just infinite. This HL-property of R is equivalent with R being a reaping family (of subsets of omega) indestructible with Sacks forcing, or equivalently some forcing adding a real. We are primarily interested in indestructible ultrafilters, we can prove the HL-property for various classical co-ideals.
Joint work with O. Guzman and M. Hrusak

We will discuss the Ramsey and other related properties in the context of Banach spaces and similar categories.

A function from one first-order structure into another first-order structure is called canonical if it sends tuples of the same type in the first structure to tuples of the same type in the second structure. This regularity notion for functions has found numerous applications in model theory, universal algebra, and theoretical computer science since its invention 7 years ago. In particular, it facilitates the understanding of self-embeddings, endomorphisms, and polymorphisms of structures, and has been applied, for example, in the classification of reducts of structures and in the study of certain computational problems related to them.
Any function between two countable structures gives rise to canonical functions in a natural way, provided its domain structure has the Ramsey property, and its goal structure is $\omega$-categorical. We outline a new proof of this fact using the framework of topological dynamics, and present the recent discovery that under certain conditions also the converse holds, i.e., the possibility of obtaining canonical functions in that way implies the Ramsey property for the domain. We moreover outline the main applications mentioned above, and the most important open problems connected to canonical functions.

For each $P\subseteq \{3,4,...,\omega\}$, we consider Wa\.zewski dendrite $W_P$, which is a compact connected metric space that we can construct in the framework of the Fraisse theory. If $P$ is finite, we prove that the universal minimal flow of the homeomorphism group $H(W_P)$ is metrizable and we compute it explicitly. This answers a question of Duchesne. If $P$ is infinite, we show that the universal minimal flow of $H(W_P)$ is not metrizable. This provides examples of topological groups which are Roelcke precompact and have a non-metrizable universal minimal flow with a comeager orbit.

Strategical Ramsey theory was developed in the nineties by Gowers in the setting of Banach spaces; it is an alternative to standard infinite-dimensional Ramsey theory in this setting where the natural pigeonhole principle does not always hold. In this talk, I will present an abstract formalism for strategical Ramsey theory, which also allows to recover more standard results relying on a pigeonhole principle, like Galvin-Prikry's theorem. As an application, I will explain how we can deduce, from this formalism, new Banach-space dichotomies.
These dichotomies are part of a common work in progress with Wilson Cuellar-Carrera and Valentin Ferenczi.

Generalizing the classical results of F. P. Ramsey from the late 1920's, the structural Ramsey theory originated at the beginning of 1970's. We say that a class $K$ of finite structures has the Ramsey property if the following holds: for any number $k \ge 2$ of colors and all $A, B \in K$ such that $A$ embeds into $B$ there is a $C \in K$ such that no matter how we color the copies of $A$ in $C$ with $k$ colors, there is a monochromatic copy $B'$ of $B$ in $C$ (that is, all the copies of $A$ that fall within $B'$ are colored by the same color).

Showing that the Ramsey property holds for a class of finite structures $K$ can be an extremely challenging task and a slew of sophisticated methods have been proposed in literature. These methods are usually constructive: given $A, B \in K$ and $k \ge 2$ they prove the Ramsey property directly by constructing a structure $C \in K$ which is Ramsey for $B$, $A$ and $k$.

In this talk we explicitly put the Ramsey property and the dual Ramsey property in the context of categories of finite structures. We use elementary category theory to generalize some combinatorial results and using the machinery of very basic category theory provide new combinatorial statements (whose formulations do not refer to category-theoretic notions) concerning both the Ramsey property and the dual Ramsey property.

We would like to stress that it was Leeb who pointed out already in early 1970's that the use of category theory can be quite helpful both in the formulation and in the proofs of results pertaining to structural Ramsey theory.

5-day workshop participants are welcome to use BIRS facilities (BIRS Coffee Lounge, TCPL and Reading Room) until 3 pm on Friday, although participants are still required to checkout of the guest rooms by 12 noon.