Topological Ramsey numbers and countable ordinals

February 1, 2019

Paul Erdős and Eric Milner published in 1972 A theorem in the partition calculus, where they established that if \beta is a countable ordinal and n\in\omega, then there is a countable ordinal \alpha such that

\alpha\to(\beta,n)^2,

meaning that any graph whose set of vertices is \alpha either contains a clique (complete subgraph) whose set of vertices H has order type \beta or an independent set of size n.

The result is false if n is replaced by \omega, except for when \beta=\omega, in which case we can take \alpha=\omega as well, this is Ramsey’s theorem.

The least \alpha such that \alpha\to(\omega+1,\omega)^2 is \alpha=\omega_1, in which case a stronger result holds, namely \omega_1\to(\omega_1,\omega+1)^2. In fact, more is true: the homogeneous set H of order type \omega_1 can be taken to be a stationary subset of \omega_1, and the set of type \omega+1 can be required to be closed, meaning that its \omegath member is the supremum of the other members of the set. Since stationary sets contain closed subsets of any countable order type, we see that \omega_1\to_{cl}(\beta,\omega+1)^2 holds for any countable ordinal \beta, where the subindex cl indicates that the sets of vertices of type \beta or \omega+1 are required to be closed on their supremum.

It is thus natural to wonder whether a closed version of the Erdős-Milner theorem holds. Jacob Hilton and I establish precisely this result in our paper Topological Ramsey numbers and countable ordinals.

This was a problem I had been curious about for a while, but kept not finding time to investigate. Finally I found a student at Boise State interested in working on this question for their master’s thesis, which gave me the perfect excuse to think seriously about it. I wrote a series of detailed notes for my student, who ended up leaving the program early, so I decided to continue and turn the notes into a paper. I even gave a preliminary talk on the results I had, together with some other results on the partition calculus of small countable ordinals. Hilton was a graduate student at that point, and he contacted me when he found out I was studying the problem, since this was precisely the topic of his dissertation. We decided to combine what we had, and soon we managed to extend our results and solve the full problem.

Many questions remain, as we believe the general bounds we found can be significantly improved, and it seems interesting to compute the optimal value of \alpha such that \alpha\to_{cl}(\beta,n)^2 for specific values of \beta<\omega_1 and n<\omega. Omer Mermelstein has some striking results in this direction.

Our paper appeared in Foundations of Mathematics, the proceedings of the conference in honor of Hugh Woodin’s 60th birthday. It can also be found on the arXiv and on my papers page.

Advertisement

Leave a Comment » | math.GN, math.LO, Papers | Tagged: , , , | Permalink
Posted by andrescaicedo

Path decompositions

April 2, 2016

On Thursday March 10, Peter Cholak gave a beautiful talk at the Logic Seminar at the University of Michigan, on Rado’s path decomposition theorem and its effective content. I want to review here some of the results covered by Peter. Slides for another version of the talk can be found in Peter’s page. This is joint work by Peter, Greg Igusa, Ludovic Patey, and Mariya Soskova. 

As usual, given a set X, let {}[X]^2 denote the collection of 2-sized subsets of X. If r is a positive integer, an r–coloring of {}[X]^2 (or simply, a coloring, if r is understood) is a map c:[X]^2\to r (where we use ordinal notation, so r=\{0,1,\dots,r-1\}).  We can think of this as a coloring using r colors of the edges of the complete graph whose underlying set of vertices is X. When r=2, we have an even simpler interpretation: A 2-coloring is just a graph on X.

Given an r-coloring  c of {}[X]^2, a path of color i\in r is a sequence a_0,a_1,\dots of distinct elements of X (which may be finite or infinite, or even empty, or of length 1) such that for all k, if a_{k+1} is defined, then c(a_k,a_{k+1})=i. Note that this is a much weaker requirement than asking that \{a_0,a_1,\dots\} be monochromatic (which would mean that c(a_k,a_j)=i for all k\ne j).  Also, in what follows X is either a finite number or \mathbb N. However, we do not require that the elements in the sequence be listed in their natural order: We may very well have that a_k>a_{k+1} for some k.

The starting point is the following observation:

Fact (Erdős).  If m is finite and c is a 2-coloring of {}[m]^2, then there are paths P_0 of color 0 and P_1 of color 1 such that every (vertex) n\in m appears in exactly one of the P_i.

In general, if c is an r-coloring of {}[X]^2, we say that P_i, i<r, is a path decomposition of c iff each P_i is a path of color i and every vertex x\in X appears in exactly one of the P_i. Using this notion, what the fact states is that for any finite m, any 2-coloring of {}[m]^2 admits a path decomposition.

Proof. Suppose the result holds for m and c is a 2-coloring of {}[m+1]^2. We can then find paths P_0 and P_1 of color 0 and 1 respectively such that each n<m appears in exactly one of the P_i. We want to show that the same holds for the full coloring (which includes edges one of whose vertices is m) at the possible expense of having to modify the partial paths we currently have. If one of the P_i is empty, this is clear. Assume then that P_0=(a_1,\dots,a_k,a_{k+1}) and P_1=(b_1,\dots,b_l,b_{l+1}). The result is also clear if c(a_{k+1},m)=0 or c(b_{l+1},m)=1. Finally, if c(a_{k+1},m)=1 and c(b_{l+1},m)=0, consider c(a_{k+1},b_{l+1}). If this color is 0, we can let the paths be P_0'=P_0{}^\frown(b_{l+1},m) and P_1'=(b_1,\dots,b_l). Similarly, if c(a_{k+1},b_{l+1})=1, we can let the paths be P_0'=(a_1,\dots,a_k) and P_1'=P_1{}^\frown(a_{k+1},m). (This is perhaps most obvious if a picture is drawn.) \Box

Rado’s paper is a generalization of this result and its countable version. The reference is

MR0485504 (58 #5334)
Rado, Richard
Monochromatic paths in graphs.
Advances in graph theory (Cambridge Combinatorial Conf., Trinity College, Cambridge, 1977).
Ann. Discrete Math. 3 (1978), 191–194.

The paper opens indicating that Erdős sketched his proof to Rado; there does not seem to be an actual reference for Erdős’s proof. Rado proceeds to prove a more general version. I will only discuss here a particular case.

First, it should be noted that, unlike typical results in Ramsey theory where, once the case of two colors is handled, the argument easily generalizes to any number of colors, the proof above does not lift to more than two. The usual way of doing this lifting is by identifying all but one of the colors. This would result in two paths P_0 and P_1, where along P_0 we only see color 0 and along P_1 we only see the other colors, but not 0. Let c be the given coloring and V be the set of vertices appearing in P_1. If the restriction of c to {}[V]^2 does not use color 0 we could indeed proceed inductively. But there is nothing to prevent 0 from being present as well, so the “easy” lifting argument actually breaks down.

The situation is indeed worse:

Theorem (Pokrovskiy). For any r>2 and any m there is an M>m and an r-coloring of {}[M]^2 that does not admit a path decomposition.

The proof can be found in:

MR3194196
Pokrovskiy, Alexey
Partitioning edge-coloured complete graphs into monochromatic cycles and paths.
J. Combin. Theory Ser. B 106 (2014), 70–97.

On the other hand, we have:

Theorem (Rado). For any finite r, any r-coloring of {}[\mathbb N]^2 admits a path decomposition.

As already mentioned, Rado’s result is more general, in particular allowing the use of countably many colors. However, the arguments that follow only apply directly to the stated version.

Before sketching the proof, note that even for r=2, the result does not follow as usual from the finite version: Given a 2-coloring c of \mathbb N, the standard approach would consist of letting P_0,P_1 be the paths resulting from successively applying Erdős’s theorem to the restrictions of c to m=2,3,\dots. But the inductive argument we presented allows the paths to be modified from one value of m to the next, which means that we cannot ensure that the process will successfully identify (via initial segments) paths for the full coloring (the partial paths do not “stabilize”). Together with Pokrovskiy’s negative result just indicated, this leaves us with a curious Ramsey-theoretic statement to which the usual compactness arguments do not apply. (Its finite counterpart, Erdős’s result, is weaker in the sense that it only applies to two colors, and requires a different argument.)

Proof. Consider a nonprincipal ultrafilter \mathcal U on \mathbb N. The ultrafilter provides us with a notion of largeness. Given r\in\mathbb N and a coloring c:[\mathbb N]^2\to r, define for x\in\mathbb N and i\in r the set of neighbors of x in color i as 

N(x,i)=\{y\mid c(x,y)=i\}.

Note that for any x the N(x,i) partition \mathbb N\setminus\{x\} and therefore there is exactly one i such that N(x,i) is large (that is, it is in $\mathcal U$). For i\in r, define

A_i=\{x\mid N(x,i)\in\mathcal U\},

and note that the A_i partition \mathbb N.

We proceed by stages to define the paths P_0,\dots,P_{r-1} as required. We set P^0_i=\emptyset for all i. In general, at the beginning of any given stage n we have defined (finite) partial approximations P^n_i to each path P_i, say P^n_i has length n_i, with P^n_i=(a_{i,1},\dots,a_{i,n_i}), using the convention that n_i=0 indicates that P^n_i=\emptyset. For each i, we will ensure that P^{n+1}_i end extends P^n_i (for all n), and simply set P_i as the resulting path. Inductively, we require that each P^n_i is a path of color i, and that if n_i>0, then a_{i,n_i}\in A_i.

Now, at stage n, we simply consider the least y not yet in any of the P^n_i. There is a unique i with y\in A_i. We set P^{n+1}_j=P^n_j for all j\ne i. If P^n_i=\emptyset, then set P^{n+1}_i=(y). Finally, if n_i>0, the point is that since N(y,i) and N(a_{i,n_i},i) are both large, then so is their intersection (all we really need is that the intersection of sets in \mathcal U is nonempty). Let x be a point in their intersection, and set P^{n+1}_i=P^n_i{}^\frown(x,y). The induction hypothesis is preserved, and this completes stage n of the construction.

It should be immediate that the P_i so constructed indeed provide a path decomposition of c, and this completes the proof. \Box

It is interesting to note that the notation just developed allows us to give a quick proof of Ramsey’s theorem for pairs: Given a coloring c:[\mathbb N]^2\to r, use notation as above, and note that for exactly one i\in r, the set A_i is in \mathcal U. We argue that there is an infinite subset H\subseteq A_i that is homogeneous for c with color i, that is, c''[H]^2=\{i\}. Indeed, we can simply set H=\{h_n\mid n\in\mathbb N\}, where the h_i are defined recursively so that h_0\in A_i and h_{j+1}\in A_i\cap\bigcap_{k\le j}N(h_k,i) for all j.

As Peter indicated in his talk, these pretty arguments are somewhat dissatisfying in that invoking a nonprincipal ultrafilter is too strong a tool for the task at hand. He then proceeded to indicate how we can in fact do better, computationally speaking. For instance, if the coloring c is computable, then we can find a path decomposition below 0''. The key to this improvement comes from two observations.

First, we do not really need an ultrafilter to carry out the argument. It suffices to consider a set C\subseteq\mathbb N that is cohesive with respect to all the N(x,i), meaning that C is infinite and, for any x,i, either C\subseteq^* N(x,i) or C\subseteq^* \mathbb N\setminus N(x,i), where \subseteq^* is the eventual containment relation: A\subseteq^* B iff there is a finite subset s of A such that A\setminus s\subseteq B, in which case we say that A is almost contained in B.

The point is that we can replace all instances where we required that a set N is in \mathcal U by the new largeness condition stating that C is almost contained in N. For instance, note that if N_1,N_2 are large, then so is their intersection. As before, for any x there is a unique i with N(x,i) large, and we can redefine A_i as the set of x such that

\exists k\,\forall y>k\,(y\in C\to c(x,y)=i),\qquad (a)

or, equivalently,

\forall k\,\exists y>k\,(y\in C\land c(x,y)=i).\qquad (b)

With these modifications, it is straightforward to verify that the proof above goes through. This shows that a path decomposition of c is \Delta^0_2(C).

In more detail: Note first that these two conditions are indeed equivalent, and second, clearly the A_i are pairwise disjoint since C is infinite and, moreover, for all x there is a unique i such that x\in A_i:

Suppose that (a) holds, and let k_0 be such that \forall y>k_0\,(y\in C\to(c(x,y)=i). Since C is infinite, we can indeed find elements y of C larger than k_0, and any such y witnesses (b).

Conversely, if (b) holds, then C\subseteq^* N(x,i), because C is cohesive and has infinite intersection with N(x,i). But then (a) holds, as wanted.

To see that any x is in a unique A_i, fix x and use that x is cohesive to conclude that if C\subseteq^*\mathbb N\setminus N(x,i) for all i, then C\subseteq^*\{x\}, which contradicts the infinitude of C. It follows that C\subseteq^* N(x,i) for some i and, since the N(x,j) are pairwise disjoint, this i is unique. This proves that (a) holds and therefore x\in A_i. Uniqueness follows from this same observation: If x\in A_i, then (as shown above) C\subseteq^* N(x,i). But there is only one i for which this is true.

The second observation is that there is an easy recursive construction of a set that is cohesive with respect to all the N(x,i): Consider first N(0,0),\dots,N(0,r-1). One of these sets is infinite (since their union is \mathbb N\setminus\{0\}), say N(0,j_0), and let a_0 be its first element. Consider now

N(0,j_0)\cap N(1,0),\dots,N(0,j_0)\cap N(1,r-1).

Their union is N(0,j_0)\setminus\{1\}, so one of these sets is infinite, say N(0,j_0)\cap N(1,j_1). Let a_1 be its first element above a_0. Etc. The set C=\{a_0,a_1,\dots\} so constructed is as wanted. Note that this construction explicitly obtains an infinite set C that, for each x, is almost contained in one the N(x,i), which is superficially stronger than being cohesive. However, as verified above, any set cohesive for all the N(x,i) must actually have this property. 

Computationally, the advantage of this construction is that it makes explicit that all we need to access a cohesive set is an oracle deciding of any N(x,i) whether it is infinite. For computable c, these are all \Pi^0_2 questions.

Peter further refined this analysis in his talk via the notion of a set being \mathsf{PA} over 0': This is any set X such that for any uniformly computable sequence of pairs of \Pi^0_2 sentences \phi_{i,0},\phi_{i,1} for i\in\mathbb N such that at least one is true, there is an f\le_T X that predicts the true sentence of each pair in the sense that for all i, if f(i)=j, then \phi_{i,j} is true. In symbols, say that X>>0'. The point of the notion is that a result of Jockusch and Stephen gives us that if X>>0' then there is a cohesive set C such that C'\le_1 X. The relevant paper is:

MR1270396 (95d:03078)
Jockusch, Carl; Stephan, Frank
A cohesive set which is not high.
Math. Logic Quart. 39 (1993), no. 4, 515–530.

MR1477624 (99a:03044)
Correction.
Math. Logic Quart. 43 (1997), no. 4, 569.

 This shows that a path decomposition for a computable coloring c can actually be found below 0''  (and more).

Peter concluded his talk by indicating how for special colorings the complexity can be further improved. For instance, say that a coloring c:[\mathbb N]^2\to r is stable iff \lim_y c(x,y) exists for all x. One can check that for stable c, we can use cofinite as a notion of largeness in the preceding arguments, and that a path decomposition can accordingly be found when c is computable below 0'. On the other hand, this is optimal, in that one can find a stable computable c such that any path decomposition computes 0'.

Leave a Comment » | math.LO, Talks | Tagged: , , , , , , , , | Permalink
Posted by andrescaicedo

187 – List of all presentations

January 10, 2012

For ease, I re-list here all the presentations we had throughout the term. I also include some of them. If you gave a presentation and would like your notes to be included, please email them to me and I’ll add them here.

  • Jeremy Elison, Wednesday, October 12: Georg Cantor and infinity.
  • Kevin Byrne, Wednesday, October 26: Alan Turing and Turing machines.
  • Keith Ward, Monday, November 7: Grigori Perelman and the Poincaré conjecture.
  • David Miller, Wednesday, November 16: Augustin Cauchy and Cauchy’s dispersion equation.
  • Taylor Mitchell, Friday, November 18: Lajos Pósa and Hamiltonian circuits.
  • Sheryl Tremble, Monday, November 28: Pythagoras and the Pythagorean theorem.
  • Blake Dietz, Wednesday, November 30: \mbox{\em Paul Erd\H os} and the Happy End problem.

Here are Jeremy’s notes on his presentation. Here is the Wikipedia page on Cantor, and a link to Cantor’s Attic, a wiki-style page discussing the different (set theoretic) notions of infinity.

Here are a link to the official page for the Alan Turing year, and the Wikipedia page on Turing. If you have heard of Conway’s Game of Life, you may enjoy the following video showing how to simulate a Turing machine within the Game of Life; the Droste effect it refers to is best explained in by H. Lenstra in a talk given at Princeton on April 3, 2007, and available here.

Here is a link to the Wikipedia page on Perelman, and the Clay Institute’s description of the Poincaré conjecture. In 2006, The New Yorker published an interesting article on the unfortunate “controversy” on the priority of Perelman’s proof.

Here are David’s slides on his presentation, and the Wikipedia page on Cauchy.

Here is a link to Ross Honsberger’s article on Pósa (including the result on Hamiltonian circuits that Taylor showed during her presentation).

Here are Sheryl’s slides on Pythagoras and his theorem. In case the gif file does not play, here is a separate copy:

The Pythagorean theorem has many proofs, even one discovered by President Garfield!

Finally, here is the Wikipedia page on \mbox{Erd\H os}. Oakland University has a nice page on him, including information on the \mbox{Erd\H os} number; see also the page maintained by Peter Komjáth, and an online depository of most of \mbox{Erd\H os's} papers.

Leave a Comment » | 187: Discrete mathematics | Tagged: , , , , , , | Permalink
Posted by andrescaicedo

580 -Partition calculus (4)

April 9, 2009

1. Colorings of pairs. I

There are several possible ways in which one can try to generalize Ramsey’s theorem to larger cardinalities. We will discuss some of these generalizations in upcoming lectures. For now, let’s highlight some obstacles.

Theorem 1 ({\mbox{\bf Erd\H os}}-Kakutani) {\omega_1\not\rightarrow(3)^2_\omega.} In fact, {2^\kappa\not\rightarrow(3)^2_\kappa.}

Proof: Let {S={}^\kappa\{0,1\}.} Let {F:[S]^2\rightarrow\kappa} be given by

\displaystyle F(\{f,g\})=\mbox{least }\alpha<\kappa\mbox{ such that }f(\alpha)\ne g(\alpha).

Then, if {f,g,h} are distinct, it is impossible that {F(\{f,g\})=F(\{f,h\})=F(\{g,h\}).} \Box

Theorem 2 (Sierpiński) {\omega_1\not\rightarrow(\omega_1)^2.} In fact, {2^\kappa\not\rightarrow(\kappa^+)^2.}

Proof: With {S} as above, let {F:[S]^2\rightarrow2} be given as follows: Let {<} be a well-ordering of {S} in order type {2^\kappa.} Let {<_{lex}} be the lexicographic ordering on {S.} Set

\displaystyle F(\{f,g\})=1\mbox{ iff }<_{lex}\mbox{ and }<\mbox{ coincide on }\{f,g\}.

Lemma 3 There is no {<_{lex}}-increasing or decreasing {\kappa^+}-sequence of elements of {S.}

Proof: Let {W=\{f_\alpha\colon\alpha<\kappa^+\}} be a counterexample. Let {\gamma\le\kappa} be least such that {\{f_\alpha\upharpoonright\gamma\colon\alpha<\kappa^+\}} has size {\kappa^+,} and let {Z\in[W]^{\kappa^+}} be such that if {f,g\in Z} then {f\upharpoonright\gamma\ne g\upharpoonright\gamma.} To simplify notation, we will identify {Z} and {W.} For {\alpha<\kappa^+} let {\xi_\alpha<\gamma} be such that {f_\alpha\upharpoonright\xi_\alpha=f_{\alpha+1} \upharpoonright\xi_\alpha} but {f_\alpha(\xi_\alpha)=1-f_{\alpha+1}(\xi_\alpha).} By regularity of {\kappa^+,} there is {\xi<\gamma} such that {\xi=\xi_\alpha} for {\kappa^+} many {\alpha.}

But if {\xi=\xi_\alpha=\xi_\beta} and {f_\alpha\upharpoonright\xi=f_\beta\upharpoonright\xi,} then {f_\beta<_{lex} f_{\alpha+1}} iff {f_\alpha<_{lex} f_{\beta+1},} so {f_\alpha=f_\beta.} It follows that {\{f_\alpha\upharpoonright\xi\colon\alpha<\kappa^+\}} has size {\kappa^+,} contradicting the minimality of {\gamma.} \Box

The lemma implies the result: If {H\subseteq S} has size {\kappa^+} and is {F}-homogeneous, then {H} contradicts Lemma 3. \Box

Now I want to present some significant strengthenings of the results above. The results from last lecture exploit the fact that a great deal of coding can be carried out with infinitely many coordinates. Perhaps surprisingly, strong anti-Ramsey results are possible, even if we restrict ourselves to colorings of pairs.

Read the rest of this entry »

4 Comments | 580: Topics in set theory | Tagged: , , , , , , , , , , , | Permalink
Posted by andrescaicedo

580 -Partition calculus (3)

April 6, 2009

1. Infinitary Jónsson algebras

Once again, assume choice throughout. Last lecture, we showed that {\kappa\not\rightarrow(\kappa)^{\aleph_0}} for any {\kappa.} The results below strengthen this fact in several ways.

Definition 1 Let {x} be a set. A function {f:[x]^{\aleph_0}\rightarrow x} is {\omega}-Jónsson for {x} iff for all {y\subseteq x,} if {|y|=|x|,} then {f''[y]^{\aleph_0}=x.}

 
Actually, for {x=\lambda} a cardinal, the examples to follow usually satisfy the stronger requirement that {f''[y]^\omega=\lambda.} In the notation from Definition 16 from last lecture, {\lambda\not\rightarrow[\lambda]^\omega_\lambda.}

The following result was originally proved in 1966 with a significantly more elaborate argument. The proof below, from 1976, is due to Galvin and Prikry.

Theorem 2 (Erdös-Hajnal) For any infinite {x,} there is an {\omega}-Jónsson function for {x.}

 
Read the rest of this entry »

6 Comments | 580: Topics in set theory | Tagged: , , , , , | Permalink
Posted by andrescaicedo

580 -III. Partition calculus

March 21, 2009

1. Introduction

Partition calculus is the area of set theory that deals with Ramsey theory; it is devoted to Ramsey’s theorem and its infinite and infinitary generalizations. This means both strengthenings of Ramsey’s theorem for sets of natural numbers (like the Carlson-Simpson or the Galvin-Prikry theorems characterizing the completely Ramsey sets in terms of the Baire property) and for larger cardinalities (like the {\mbox{Erd\H os}}-Rado theorem), as well as variations in which the homogeneous sets are required to possess additional structure (like the Baumgartner-Hajnal theorem).

Ramsey theory is a vast area and by necessity we won’t be able to cover (even summarily) all of it. There are many excellent references, depending on your particular interests. Here are but a few:

  • Paul {\mbox{Erd\H os},} András Hajnal, Attila Máté, Richard Rado, Combinatorial set theory: partition relations for cardinals, North-Holland, (1984).
  • Ronald Graham, Bruce Rothschild, Joel Spencer, Ramsey theory, John Wiley & Sons, second edn., (1990).
  • Neil Hindman, Dona Strauss, Algebra in the Stone-{\mbox{\bf \v Cech}} compactification, De Gruyter, (1998).
  • Stevo {\mbox{Todor\v cevi\'c},} High-dimensional Ramsey theory and Banach space geometry, in Ramsey methods in Analysis, Spiros Argyros, Stevo {\mbox{Todor\v cevi\'c},} Birkhäuser (2005), 121–257.
  • András Hajnal, Jean Larson, Partition relations, in Handbook of set theory, Matthew Foreman, Akihiro Kanamori, eds., to appear.

I taught a course on Ramsey theory at Caltech a couple of years ago, and expect to post notes from it at some point. Here we will concentrate on infinitary combinatorics, but I will briefly mention a few finitary results.

Read the rest of this entry »

9 Comments | 580: Topics in set theory | Tagged: , , , , , , , , , , , | Permalink
Posted by andrescaicedo