Examples from infinitary combinatorics

Abstract:

In the classical times of combinatorics, people like Erdös or Rado did both finite and infinite combinatorics being able to exploit arguments coming from one area in the other, if possible. Nowadays finite and infinite methods became more specialized and separate. Still one can state interesting questions both in finite and infinite versions which often have different answers. But what about combinatorial arguments, shouldn't deep combinatorial arguments have both finite and infinite forms (possibly with completely different implications)?

In this talk we present some developments in (infinite) set-theory which could possibly remind finite combinatorists some aspects of their field (with usually different results). We will attempt to present these topics without assuming any knowledge of the uncountable or the undecidable. We will try to focus on the combinatorial content distinguishing four magnitudes: the finite, the countable, the first uncountable $\omega_1$ and the second uncountable $\omega_2$. The concepts which express interactions between these magnitudes have analog concepts for finite numbers. We hope that through this analogy a clear combinatorial picture will be visible. We will focus on the following two topics, close to our own field of research, which are deeply related.

1. The failure of the Ramsey property for the uncountable witnessed dramatic developments in last 10-15 years. New colorings of pairs with totally unexpected properties have been constructed by Todorcevic. Since then interesting structures like uncountable groups, nonseparable Banach spaces, or topological spaces have been obtained using this combinatorics and solving open problems in the related areas.

Although in the finite or countable realm we have the Ramsey property, we are in deep need of constructions of colorings of pairs from finite sets without large homogeneous subsets (E.g. an open problem of finding colorings witnessing $R(n)>(1+\varepsilon)^n$). And so there is a common need in both finite and the uncountable combinatorics of new ideas in partitioning pairs.

2. The compactness theorem for hypergraphs doesn't have a version which involves countable chromatic number (works just for finite chromatic number), in the case of graphs of the size $\omega_1$ it is trivial. The deep combinatorics starts at the second uncountable cardinal $\omega_2$. Here constructions of graphs $G$ of uncountable chromatic number such that every subgraph $H$ of $G$ of size $\omega_1$ has countable chromatic number have been dynamic part of set theory. Results involving graphs like $(A,B)\in E(G)$ iff $A\cap B\not=\emptyset$ for sets $A,B$ or $(p,q)\in E(G)$ iff $p\leq q$ or $q\leq p$ for partial orders like trees has been obtained (mainly by Todorcevic) using new combinatorial arguments. Again, a finite analog could be described as a big graph $G$ whose chromatic number is not small but every subgraph of $G$ of medium size has a small chromatic number. On the other hand Shelah obtained a version of compactness theorem which works just for some structures (deep applications in group theory related to Whitehead groups) and some cardinals. This is also related to the problem of the existence of transversals for infinite families of sets solved in several papers by Shelah and Milner.