On the maximum number of integer colourings with forbidden monochromatic sums, Hong Liu, Maryam Sharifzadeh and Katherine Staden
Maryam spoke about this paper at this week’s combinatorics seminar.
The problem is as follows. Let be the number of
-colourings of a subset
of
with no monochromatic sum
. What is the maximum
of
over all
?
One possibility is that we take to be sum-free, so that
. The maximum size of a sum-free set of
is around
, achieved by the set
of odd numbers and the interval
, so
.
Another possibility is to choose sum-free sets
and take all colourings of
such that the elements of colour
are contained in
. There are
such colourings, where is the number of elements in exactly
of the
. For example, we might take half of the
to be
and half to be
. Then the odd numbers greater than
are in every set, and the evens greater than
and the odds less than
are in half of the sets, so the number of colourings is around
For this matches the previous lower bound; for
it is larger.
It’s easy to see that this construction cannot improve the bound for : it only provides
good colourings, but
as elements contributing to
are in
, which must be sum-free.
What about ? Now we get
good colourings. We also have that
But since we have
Moreover, if is not tiny then we are some distance off this upper bound, so the only good constructions in this family come from having all the
substantially agree.
How can we get matching upper bounds? If there weren’t very many maximal sum-free sets then we could say that every good colouring arises from a construction like this, and there aren’t too many such constructions to consider. This is too optimistic, but the argument can be patched up using containers.
The container method is a relatively recent addition to the combinatorial toolset. For this problem the key fact is that there is a set of
subsets of
such that
- every sum-free set is contained in some
,
- each
is close to sum-free. Combined with a “sum-removal lemma” this means in particular that it has size not much larger than
.
We now consider running the above construction with each an element of
. Since the containers are not themselves sum-free, this will produce some bad colourings. But because every sum-free set is contained in some element of
, every good colouring of a subset
of
will arise in this way. And since there are most
choices for the sets
the number of colourings we produce is at most a factor
greater than the biggest single example arising from the construction.
This is the big idea of the paper: it reduces counting colourings to the problem of optimising this one construction. For the authors are able to solve this new problem, and so the original.