Warning: Cannot modify header information - headers already sent by (output started at /home/public/wp-content/themes/simplelin/functions.php:1) in /home/public/wp-includes/rest-api/class-wp-rest-server.php on line 1713

Warning: Cannot modify header information - headers already sent by (output started at /home/public/wp-content/themes/simplelin/functions.php:1) in /home/public/wp-includes/rest-api/class-wp-rest-server.php on line 1713

Warning: Cannot modify header information - headers already sent by (output started at /home/public/wp-content/themes/simplelin/functions.php:1) in /home/public/wp-includes/rest-api/class-wp-rest-server.php on line 1713

Warning: Cannot modify header information - headers already sent by (output started at /home/public/wp-content/themes/simplelin/functions.php:1) in /home/public/wp-includes/rest-api/class-wp-rest-server.php on line 1713

Warning: Cannot modify header information - headers already sent by (output started at /home/public/wp-content/themes/simplelin/functions.php:1) in /home/public/wp-includes/rest-api/class-wp-rest-server.php on line 1713

Warning: Cannot modify header information - headers already sent by (output started at /home/public/wp-content/themes/simplelin/functions.php:1) in /home/public/wp-includes/rest-api/class-wp-rest-server.php on line 1713

Warning: Cannot modify header information - headers already sent by (output started at /home/public/wp-content/themes/simplelin/functions.php:1) in /home/public/wp-includes/rest-api/class-wp-rest-server.php on line 1713

Warning: Cannot modify header information - headers already sent by (output started at /home/public/wp-content/themes/simplelin/functions.php:1) in /home/public/wp-includes/rest-api/class-wp-rest-server.php on line 1713
{"id":369,"date":"2017-11-30T17:09:14","date_gmt":"2017-11-30T17:09:14","guid":{"rendered":"http:\/\/babarber.uk\/?p=369"},"modified":"2017-11-30T17:09:14","modified_gmt":"2017-11-30T17:09:14","slug":"counting-colourings-with-containers","status":"publish","type":"post","link":"https:\/\/babarber.uk\/369\/counting-colourings-with-containers\/","title":{"rendered":"Counting colourings with containers"},"content":{"rendered":"

On the maximum number of integer colourings with forbidden monochromatic sums<\/a>,\u00a0Hong Liu, Maryam Sharifzadeh and Katherine Staden<\/p>\n

Maryam spoke about this paper at this week’s combinatorics seminar.<\/p>\n

The problem is as follows.\u00a0 Let $\"f(A, r)\"$ be the number of $\"r\"$ -colourings of a subset $\"A\"$ of $\"[n]\"$ with no monochromatic sum $\"x + y = z\"$ .\u00a0 What is the maximum $\"f(n,r)\"$ of $\"f(A, r)\"$ over all $\"A \subseteq [n]\"$ ?<\/p>\n

One possibility is that we take $\"A\"$ to be sum-free, so that $\"f(A, r) = r^{|A|}\"$ .\u00a0 The maximum size of a sum-free set of $\"[n]\"$ is around $\"n/2\"$ , achieved by the set $\"O\"$ of odd numbers and the interval $\"I = [\lfloor n/2 \rfloor + 1, n]\"$ , so $\"f(n, r) \geq r^{n/2}\"$ .<\/p>\n

Another possibility is to choose $\"r\"$ sum-free sets $\"A_1, \ldots, A_r\"$ and take all colourings of $\"A = A_1 \cup \cdots \cup A_r\"$ such that the elements of colour $\"i\"$ are contained in $\"A_i\"$ .\u00a0 There are <\/p>\n

<\/span> <\/span> $\"\[1^{n_1} \cdot 2^{n_2} \cdots r^{n_r}\]\"$ <\/p>\n

such colourings, where $\"n_j\"$ is the number of elements in exactly $\"j\"$ of the $\"A_i\"$ .\u00a0 For example, we might take half of the $\"A_i\"$ to be $\"O\"$ and half to be $\"I\"$ .\u00a0 Then the odd numbers greater than $\"n/2\"$ are in every set, and the evens greater than $\"n/2\"$ and the odds less than $\"n/2\"$ are in half of the sets, so the number of colourings is around <\/p>\n

<\/span> <\/span> $\"\[r^{n/4}(r/2)^{n/2}.\]\"$ <\/p>\n

For $\"r=4\"$ this matches the previous lower bound; for $\"r \geq 5\"$ it is larger.<\/p>\n

It’s easy to see that this construction cannot improve the bound for $\"r = 2\"$ : it only provides $\"2^{n_2}\"$ good colourings, but $\"n_2 \leq n/2\"$ as elements contributing to $\"n_2\"$ are in $\"A_1 \cap A_2\"$ , which must be sum-free.<\/p>\n

What about $\"r=3\"$ ?\u00a0 Now we get $\"2^{n_2}3^{n_3} = 3^{n^3 + n_2 / \log_2 3}\"$ good colourings.\u00a0 We also have that<\/p>\n

<\/span> <\/span> $\"\[2n_2 + 3n_3 \leq |A_1| + |A_2| + |A_3| \leq 3n/2.\]\"$ <\/p>\n

But since $\"\log_2(3) > 3/2\"$ we have <\/p>\n

<\/span> <\/span> $\"\[3^{n^3 + n_2 / \log_2 3} \leq 3^{n^3 + 2n_2 / 3} \leq 3^{n/2}.\]\"$ <\/p>\n

Moreover, if $\"n_2\"$ 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 $\"A_i\"$ substantially agree.<\/p>\n

How can we get matching upper bounds?\u00a0 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.\u00a0 This is too optimistic, but the argument can be patched up using\u00a0containers<\/em>.<\/p>\n

The container method is a relatively recent addition to the combinatorial toolset.\u00a0 For this problem the key fact is that there is a set $\"\mathcal F\"$ of $\"2^{o(n)}\"$ subsets of $\"[n]\"$ such that<\/p>\n

\n
every sum-free set is contained in some $\"F \in \mathcal F\"$ ,<\/li>\n
each $\"F \in \mathcal F\"$ is close to sum-free.\u00a0 Combined with a “sum-removal lemma” this means in particular that it has size not much larger than $\"n/2\"$ .<\/li>\n<\/ul>\n
We now consider running the above construction with each $\"A_i\"$ an element of $\"\mathcal F\"$ .\u00a0 Since the containers are not themselves sum-free, this will produce some bad colourings.\u00a0 But because every sum-free set is contained in some element of $\"\mathcal F\"$ , every good colouring of a subset $\"A\"$ of $\"[n]\"$ will arise in this way.\u00a0 And since there are most $\"|\mathcal F|^r\"$ choices for the sets $\"A_i\"$ the number of colourings we produce is at most a factor $\"2^{o(n)}\"$ greater than the biggest single example arising from the construction.<\/p>\n
This is the big idea of the paper: it reduces counting colourings to the problem of optimising this one construction.\u00a0 For $\"r \leq 5\"$ the authors are able to solve this new problem, and so the original.<\/p>\n
<\/p>\n","protected":false},"excerpt":{"rendered":"
On the maximum number of integer colourings with forbidden monochromatic sums,\u00a0Hong Liu, Maryam Sharifzadeh and Katherine Staden Maryam spoke about this paper at this week’s combinatorics seminar. The problem is as follows.\u00a0 Let be the number of -colourings of a subset of with no monochromatic sum .\u00a0 What is the maximum of over all ? … <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[4],"tags":[9,33],"_links":{"self":[{"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/posts\/369"}],"collection":[{"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/comments?post=369"}],"version-history":[{"count":0,"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/posts\/369\/revisions"}],"wp:attachment":[{"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/media?parent=369"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/categories?post=369"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/tags?post=369"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}