Monochromatic colorings

August 20, 2016

Caïus Wojcik and Luca Zamboni recently posted a paper on the arXiv solving an interesting problem in combinatorics on words.

http://arxiv.org/abs/1608.03519
Monochromatic factorisations of words and periodicity.
Caïus Wojcik, Luca Q. Zamboni.

I had recently learned of the problem through another paper by Zamboni and a collaborator,

MR3425965
Aldo de Luca, Luca Q. Zamboni
On prefixal factorizations of words.
European J. Combin. 52 (2016), part A, 59–73.

It is a nice result and I think it may be enjoyable to work through the argument here. Everything that follows is either straightforward, standard, or comes from these papers.

1. The problem

To make the post reasonably self-contained, I begin by recalling some conventions, not all of which we need here.

By an alphabet we simply mean a set A, whose elements we refer to as letters. A word w is a sequence w:N\to A of letters from A where N is a (not necessarily non-empty, not necessarily proper) initial segment of \mathbb N. If we denote w_i=w(i) for all i\in N, it is customary to write the word simply as

w_0w_1\dots

and we will follow the convention. The empty word is typically denoted by \Lambda or \varepsilon. By A^* we denote the collection of all finite words from A, and A^+=A^*\setminus \{\varepsilon\}. By |x| we denote the length of the word x (that is, the size of the domain of the corresponding function).

We define concatenation of words in the obvious way, and denote by x_0x_1 the word resulting from concatenating the words x_0 and x_1, where x_0\in A^*. This operation is associative, and we extend it as well to infinite concatenations.

If a word w can be written as the concatenation of words x_0,x_1,\dots,

w=x_0x_1\dots,

we refer to the right-hand side as a factorization of w. If w=xy and x is non-empty, we say that x is a prefix of w. Similarly, if y is non-empty, it is a suffix of w. By x^n for n\in\mathbb N we denote the word resulting form concatenating n copies of x. Similarly, x^{\mathbb N} is the result of concatenating infinitely many copies.

By a coloring we mean here a function c:A^+\to C where C is a finite set of “colors”.

Apparently the problem I want to discuss was first considered by T.C. Brown around 2006 and, independently, by Zamboni around 2010. It is a question about monochromatic factorizations of infinite words. To motivate it, let me begin with a cute observation.

Fact. Suppose w=w_0w_1\dots is an infinite word, and c is a coloring. There is then a factorization 

w=px_0x_1\dots 

where all the x_i\in A^+ have the same color.

Proof. The proof is a straightforward application of Ramsey’s theorem: Assign to c the coloring of the set [\mathbb N]^2 of 2-sized subsets of \mathbb N given by d(\{i,j\})=c(w_iw_{i+1}\dots w_{j-1}) whenever i<j. Ramsey’s theorem ensures that there is an infinite set I=\{n_0<n_1<\dots\} such that all w_{n_i}w_{n_i+1}\dots w_{n_j-1} with i<j have the same color. We can then take p=w_0\dots w_{n_0-1} and x_i=w_{n_i}\dots w_{n_{i+1}-1} for all i. \Box

In the fact above, the word w was arbitrary, and we obtained a monochromatic factorization of a suffix of w. However, without additional assumptions, it is not possible to improve this to a monochromatic factorization of w itself. For example, consider the word w=01^{\mathbb N} and the coloring

c(x)=\left\{\begin{array}{cl}0&\mbox{if }0\mbox{ appears in }x,\\ 1&\mbox{otherwise.}\end{array}\right.

If nothing else, it follows that if w is an infinite word that admits a monochromatic factorization for any coloring, then the first letter of w must appear infinitely often. The same idea shows that each letter in w must appear infinitely often.

Actually, significantly more should be true. For example, consider the word

w=010110111\dots 01^n0 1^{n+1}\dots,

and the coloring

c(x)=\left\{\begin{array}{cl}0&\mbox{if }x\mbox{ is a prefix of }w,\\1&\mbox{otherwise.}\end{array}\right.

This example shows that in fact any such w must admit a prefixal factorization, a factorization

w=x_0x_1\dots

where each x_i is a prefix of w.

Problem. Characterize those infinite words w with the property P that given any coloring, there is a monochromatic factorization of w.

The above shows that any word with property P admits a prefixal factorization. But it is easy to see that this is not enough. For a simple example, consider

w=010^210^31\dots0^n10^{n+1}1\dots

Consider the coloring c where c(x)=0 if x is not a prefix of w, c(0)=1, and c(x)=2 otherwise. If

w=x_0x_1\dots

is a monochromatic factorization of w, then x_0=01\dots so c(x_0)=2 and each x_i must be a prefix of w of length at least 2. But it is easy to see that w admits no such factorization: For any n>2, consider the first appearance in w of 0^{n+1} and note that none of the first n zeros can be the beginning of an x_i, so for some j we must have x_j=01\dots 10^n and since n>2, in fact x_j=01\dots 10^n10^n, but this string only appears once in w, so actually j=0. Since n was arbitrary, we are done.

Here is a more interesting example: The Thue-Morse word

t=0110100110010110\dots

was defined by Axel Thue in 1906 and became known through the work of Marston Morse in the 1920s. It is defined as the limit (in the natural sense) of the sequence x_0,x_1,\dots of finite words given by x_0=0 and x_{n+1}=x_n\bar{x_n} where, for x\in\{0,1\}^*, \bar x is the result of replacing each letter i in x with 1-i.

This word admits a prefixal factorization, namely

t=(011)(01)0(011)0(01)(011)(01)0(01)(011)0(011)(01)0\dots

To see this, note that the sequence of letters of t can be defined recursively by t_0=0, t_{2n}=t_n and t_{2n+1}=1-t_n. To see this, note in turn that the sequence given by this recursive definition actually satisfies that t_n is the parity of the number of 1s in the binary expansion of n, from which the recursive description above as the limit of the x_n should be clear. The relevance of this observation is that no three consecutive letters in t can be the same (since t_{2n+1}=1-t_{2n} for all n), and from this it is clear that t can be factored using only the words 0, 01, and 011.

But it is not so straightforward as in the previous example to check whether t admits a factorization into prefixes of length larger than 1.

Instead, I recall a basic property of t and use it to exhibit an explicit coloring for which t admits no monochromatic factorization.

Read the rest of this entry »

Advertisement

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

Ramsey theory of very small countable ordinals

November 6, 2014

I was an undergraduate student at Los Andes, from 1992 to 1996. This year, their mathematics program is turning 50. There was a conference in September to celebrate the event, and I had the honor to give one of the talks (see here for the English version of the slides).

The Faculty of Science publishes a magazine, Hipótesis, and a special edition will be devoted to the conference. I have submitted an expository paper, based on my talk.

The topic is the partition calculus of very small countable ordinals (mainly ordinals below \omega^2, actually). The paper reviews Ramsey’s theorem and a few finite examples, before discussing the two main results.

1.

One is an old theorem by Haddad and Sabbagh, unfortunately not well known. In 1969, they computed the Ramsey numbers r(\omega+n,m) for n,m finite.

Given nonzero ordinals \alpha,\beta, recall that r(\alpha,\beta) is the least \gamma such that any red-blue coloring of the edges of K_\gamma either admits a red copy of K_{\alpha} or a blue copy of K_\beta. Clearly r(\alpha,1)=1, r(\alpha,\beta)\ge r(\alpha,2)=\alpha if \beta\ge2, and r(\alpha,\beta)=r(\beta,\alpha), so we may as well assume that \alpha\ge\beta>2, and we adopt this convention in what follows.

Ramsey proved two theorems about this function in a famous 1928 paper that introduced the topic. In the notation we have just set up, his first result asserts that r(n,m) is finite whenever n,m are finite, and his second result states that r(\omega,\omega)=\omega. The computation of the numbers r(n,m) is an extremely difficult, most likely unfeasible, problem, though r is obviously a recursive function. We are concerned here with the values of the function when at least one of the arguments is infinite.

It turns out that r(\omega+1,\omega) is already \omega_1. Hence, if we are interested in studying the countable values of the function r(\alpha,\beta), then we must assume that either \omega=\alpha, in which case r(\alpha,\beta)=\omega and there is nothing more to say, or else (that is, if \alpha is countable and strictly larger than \omega) we must assume that \beta is finite.

The function has been intensively studied when \alpha is a limit ordinal, particularly a power of \omega. Here we look at the much humbler setting where \omega<\alpha<\omega2. Recalling that each ordinal equals the set of its predecessors, and using interval notation to describe sets of ordinals, the Haddad-Sabbagh result is as follows:

Lemma. For all positive integers n, m there exists a positive integer k\ge n, m such that for any red-blue coloring of the edges of K_{[0,k)}, and such that K_{[0,m)} is blue, there is a subset H of {}[0, k) with K_H monochromatic, and either K_H is blue and |H| = m + 1, or else K_H is red, |H|=n+1, and H\cap[0,m)\ne\emptyset.

Denote by r_{HS}(n+1,m+1) the smallest number k witnessing the lemma.

Theorem. If n,m are positive integers, then r(\omega +n,m)=\omega(m-1)+t, where r_{HS}(n+1,m)=(m-1)+t.

The theorem was announced in 1969, but the proof never appeared. I have written a survey on the topic, including what should be the first proof in print of this result.

Read the rest of this entry »

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

502 – König’s lemma (2)

August 26, 2009

We continue with the example of domino systems.

Remark 1 There is no algorithm that determines whether a given {D} can tile the plane or not.

Of course, for specific systems {D,} we usually can tell by ad hoc methods which one is the case. What the remark above indicates is that there is no uniform way of doing this.

Read the rest of this entry »

3 Comments | 502: Logic and 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