Partition regularity and other combinatorial problems

This is the imaginative title of my PhD thesis.  It contains four unrelated pieces of work.  (I was warned off using this phrasing in the thesis itself, where the chapters are instead described as “self-contained”.)

The first and most substantial concerns partition regularity.  It is a coherent presentation of all of the material from Partition regularity in the rationals, Partition regularity with congruence conditions and Partition regularity of a system of De and Hindman.

The remaining three chapters are expanded versions of Maximum hitting for sufficiently large, Random walks on quasirandom graphs and A note on balanced independent sets in the cube.1

1 “A note … ” was fairly described by one of my examiners as a “potboiler”.  It was also my first submitted paper, and completed in my second of three years.  Perhaps this will reassure anybody in the first year of a PhD who is worrying that they have yet to publish.

Distinguishing subgroups of the rationals by their Ramsey properties

In Partition regularity in the rationals we (Barber, Hindman and Leader) showed that there are systems of equations that are partition regular over but not over . Here we show that this separation is very strong: there is an uncountable chain of subgroups from to such that each subgroup has a system that is partition regular over it but over no earlier subgroup. We use our new central sets approach, but this result could also have been proved using the original density method.

Most of the work in this paper is spent proving that the systems we construct are strongly partition regular, in the sense that the variables can be forced to take different values. If you only want to see the application then you can skip part of the argument without losing anything.

Partition regularity without the columns property

Rado’s theorem states that a finite matrix is partition regular if and only if it has the “columns property”. It is easy to write down infinite matrices with the columns property that are not partition regular, but all known examples of partition regular matrices do have the columns property. In this paper we describe a matrix that is partition regular but fails to have the columns property in the strongest possible sense.

The main contribution of this paper is a translation of the key lemma of “Partition regularity in the rationals” to work with central, rather than dense, sets. Central sets have very strong combinatorial properties; for example, they contain solutions to all finite partition regular systems. As a result, our theorems are harder to prove but easier to apply—for the application above we could have proved the partition regularity of the systems using density methods, but the argument would have been more involved.

Partition regularity of a system of De and Hindman

De and Hindman proposed that a particular system should be partition regular but not partition regular near zero. With Neil Hindman and Imre Leader I found a different example; in this paper I show that De and Hindman’s original system also works.

Partition regularity with congruence conditions

Does a partition regular system remain partition regular if we ask that each variable is divisible by ? Not necessarily. This answers several open questions from Hindman, Leader and Strauss’s 2003 survey.

The proof of Proposition 5 in the journal version is not entirely clear; I recommend reading the updated pdf linked above. My thanks to Boaz Tsaban for pointing this out.

Partition regularity in the rationals

A system of linear equations is partition regular if, whenever the natural numbers are finitely coloured, the system of equations has a monochromatic solution. Partition regularity can also be defined over the rationals, and if the system of equations is finite then these notions coincide. We construct an example of an infinite system which is partition regular over the rationals but not the naturals. The proof is based on examining what happens when you take iterated sumsets and difference sets of subsets of the integers with positive upper density.

Ultrafilter quantifiers and Hindman’s theorem

A filter on is a consistent notion of largeness for subsets of . “Largeness” has the following properties.

• if is large and then is large
• if and are large then is large
• the empty set is not large

At most one of and is large; an ultrafilter is a filter which always has an opinion about which it is.

• either or is large

The usual notation for “ is large” is , where is the ultrafilter. This casts ultrafilters as sets, rather than notions of largeness. To bring the notion of largeness to the foreground we can use ultrafilter quantifiers; we write , read “for -most , holds” (where we have also identified with the predicate “is a member of “).

• if and then
• if and then

From this point of view says that the set of elements with property is everything, and that the set of elements with property is non-empty. behaves like a mixture of and , with the considerable advantage that logical operations pass through unchanged without having to worry about De Morgan’s laws.

It turns out that the set of ultrafilters on is a model for the Stone–Čech compactification of . is embedded as the set of principal ultrafilters (“ is large if and only if “), and the addition on extends to :

(Here should be interpreted as .) But to use this addition with quantifiers all we need to know is that . If you can see that from the first definition then your brain is wired differently from mine.

It is a fact that there exist idempotent ultrafilters, with . Given such a , we can play the following game. Suppose that . Then , so and therefore (by ANDing with the original assertion, and the original assertion with the dummy variable replaced by ). In particular, . But now we can fix a good choice of and repeat the whole process with in place of to get that

Iterating, we eventually obtain an infinite sequence such that holds for every sum of finitely many of the . Together with the observation that whenever is finitely coloured exactly one of the colour classes is -large this proves Hindman’s theorem, that we can always find an infinite sequence such that every sum of finitely many terms has the same colour.

A version of this argument with more of the details filled in is on the Tricki.

Piecewise syndetic and van der Waerden

Joel Moreira has just proved that whenever the natural numbers are finitely coloured we can find and such that , and are all the same colour.  He actually proves a much more general result via links to topological dynamics, but he includes a direct proof of this special case assuming only a consequence of van der Waerden’s theorem related to piecewise syndetic sets.  I want to record the details here so that I remember them in future.

Syndetic, thick and piecewise syndetic

A set of natural numbers is thick if it contains (arbitrarily) long intervals, and syndetic if it has bounded gaps. It is piecewise syndetic if it has bounded gaps on long intervals (the same bound for each interval).

Piecewise syndetic sets are partition regular:

Claim. If is piecewise syndetic then either or is. (This extends to partitions into more parts by induction.)

Proof. Choose intervals of length on which the gaps in are bounded by . Suppose that is not piecewise syndetic. Then for every there is an such that has a gap more than points wide. So contains an interval of length on which its gaps are bounded by .

It follows that, whenever the natural numbers are finitely coloured, one of the colour classes is piecewise syndetic. So to prove van der Waerden’s theorem it would suffice to show that every piecewise syndetic set has long arithmetic progressions. We’ll prove this apparent strengthening, assuming van der Waerden’s theorem itself.

Claim. If is piecewise syndetic, then it contains long APs.

Proof. If has long intervals with gaps bounded by , then the union of the translates of contains long intervals. So can be viewed as a -colouring of a set of long intervals, hence one of them contains long APs by van der Waerden’s theorem. But they are all translates of , so contains long APs.

In fact we can say much more: for every there is a such that the set of such that the AP of length and common difference starting at is contained in is piecewise syndetic. To see this, let be a block of consecutive integers sufficiently long that whenever it is -coloured it contains an AP of length . Pack translates of greedily into the intervals in . For each translate of there is a triple such that contains the AP of length and common difference starting at . Now the set of is piecewise syndetic (it has long intervals with gaps bounded by ). And there are only finitely many choices for (at most ) and (at most ). So by the first claim there is some choice of such that the corresponding are piecewise syndetic. That is, the set is piecewise syndetic. This is Theorem 5.1 in Moreira’s paper, with and . The case of general follows by taking .