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 »


Smullyan

August 11, 2016

I have just posted on my papers page a preprint of a review of

MR3379889
Smullyan, Raymond
Reflections—the magic, music and mathematics of Raymond Smullyan.
World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ, 2015. x+213 pp.
ISBN: 978-981-4644-58-7; 978-981-4663-19-9

that I have submitted to Mathematical Reviews.


MSC2020

July 26, 2016

Announcement of the plan to revise the Mathematics Subject Classification

Mathematical Reviews (MR) and zbMATH cooperate in maintaining the Mathematics Subject Classification (MSC), which is used by these reviewing services, publishers, and others to categorize items in the mathematical sciences literature. The current version, MSC2010, consists of 63 areas classified with two digits refined into over 5000 three- and five-digit classifications. Details of MSC2010 can be found at www.msc2010.org or www.ams.org/msc/msc2010.html and zbmath.org/classification/.

MSC2010 was a revision of the 2000 subject classification scheme developed through the collaborative efforts of the editors of zbMATH and MR with considerable input from the community. zbMATH and MR have initiated the process of revising MSC2010 with an expectation that the revision will be used beginning in 2020. From the perspective of MR and zbMATH, the five-digit classification scheme MSC is an extremely important device that allows editors and reviewers to process the literature. Users of the publications of zbMATH and MR employ the MSC to search the literature by subject area. In the decade since the last revision, keyword searching has become increasingly prevalent, with remarkable improvements in searchable databases. Yet, the classification scheme remains important. Many publishers use the subject classes at either the time of submission of an article, as an aid to the editors, or at the time of publication, as an aid to readers. The arXiv uses author-supplied MSC codes to classify submissions, and as an option in creating alerts for the daily listings. Browsing the MR or zbMATH database using a two- or three-digit classification search is an effective method of keeping up with research in specific areas.

Based in part on some thoughtful suggestions from members of the community, the editors of MR and zbMATH have given preliminary consideration to the scope of the revision of the MSC. We do not foresee any changes at the two-digit level; however, it is anticipated that there will be refinement of the three- and five-digit levels.

At this point, zbMATH and MR welcome additional community input into the process. Comments should be submitted through the Web at msc2020.org. You may also send email to feedback@msc2020.org. All information about the MSC revision is jointly shared by MR and zbMATH. This input will be of great value as the process moves forward.

Edward Dunne, Executive Editor, Mathematical Reviews
Klaus Hulek, Editor-in-Chief, zbMATH

Version of 2016.07.25

Help!

July 5, 2016

IMG_3359

Help us identify all mathematicians in this picture (click on it for a larger version). Please post comments here, on G+, or email me or Paul Larson.

The picture will appear in the book of proceedings of the Woodin conference, http://logic.harvard.edu/woodin_meeting.html. (Thanks to David Schrittesser for allowing us to use it.)


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 rcoloring 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'.


Ian Cavey on sphere bounded regions

October 10, 2015

I met Ian Cavey, an undergraduate at Boise State, about a year ago. He took my Communication in the mathematical sciences course. It was a pleasure to have him as a student. (You can see the slides of one of his group projects here.)

Last Spring, Ian took my advanced linear algebra class. Also, he told me he was interested in trying some independent research under my guidance. He proved to be quite independent (he chose the problem he wanted to work on) and resourceful (for instance, finding workarounds when his direct approach would not work). The result of this was a paper (Volumes of Sphere-Bounded Regions in High Dimensions) that he presented at the recent MAA centennial meeting (see page 18 of the program). You can see his slides here.

[You can see Norm Richert representing Math Reviews at the meeting in this post.]

At the conference, Ian not only presented his talk. He also competed and won first place in the US National Collegiate Mathematics Championship. Some additional details can be found here.

Ian’s talk is about his approach to estimate the n-dimensional volume of the central region of a unit n-cube bounded by n-spheres centered at the vertices. Ian proves that this volume quickly approaches 1. His slides detail his nice combinatorial argument that circumvents the need for explicit computations of unwieldy iterated integrals.


Amazing grace

June 29, 2015

I.

lead_large

(Photo by Chuck Burton)

At least six black churches burned last week.

img_2901-1

(Photo by Adam Anderson)

Bree Newsome has been charged with “defacing monuments on state Capitol grounds”, which holds a fine of up to $5,000, and “a prison term of up to three years or both.”

White House

(See here.)

II.

So, we moved to Ann Arbor.

20150612_211727

We visited the Hands-On Museum (thanks to Zach and Diana, and congratulations!),

20150625_152906

and attended the Math Reviews Summer picnic.

20150626_13273120150626_162603

I started today.

20150629_112608


Follow

Get every new post delivered to your Inbox.

Join 73 other followers