15
$\begingroup$

The diagonal Ramsey number $R(n,n)$ is the least number $m$ for which the following holds: in any edge-colouring of the complete graph $K_m$ in which each edge is coloured blue or red, there is a monochromatic $K_n.$

The list Ramsey number (my name for it) $R_\ell(n)$ is the least number $m$ for which the following holds: we can assign to each edge of the complete graph $K_m$ a list of two distinct colours so that, in any edge-colouring of $K_m$ where each edge receives a colour from its assigned list, there is a monochromatic $K_n.$

This definition is what we get if we regard the diagonal cases of Ramsey's theorem as assertions about the chromatic numbers of certain hypergraphs, and then replace chromatic numbers with list chromatic numbers.

Plainly $R_\ell(n)\le R(n,n),$ since we can simply assign the list $\{\text{blue, red}\}$ to each edge.

On the other hand, the probabilistic lower bound works just the same for $R_\ell(n)$ as for $R(n,n),$ so we have $R_\ell(n)\ge2^{n/2}.$

Questions. Have such things been studied? Does it ever happen that $R_\ell(n)\lt R(n,n)$?

Of course we can define analogous variants of the (diagonal) multicolour and hypergraph Ramsey numbers, but maybe the above is enough insanity for today.


P.S. In a comment Thomas Bloom brought up the list colouring conjecture, which says that the list edge chromatic number of any graph is equal to the ordinary edge chromatic number. Here is a common generalization of the list coloring conjecture (for simple graphs) and the conjecture that $R_\ell(n)=R(n,n)$:

General Conjecture. For any simple finite graphs $G$ and $H$ and any $c\in\mathbb N$ the following statements are equivalent:

(a) any edge-colouring of $G$ with at most $c$ colours contains a monochromatic copy of $H$;

(b) we can assign to each edge of $G$ a list of $c$ distinct colours so that, in any edge-colouring of $G$ where each edge receives a colour from its assigned list, there is a monochromatic copy of $H.$

This reduces to the list colouring conjecture (for simple graphs) when $H=K_{1,2},$ and it reduces to my question about $R_\ell(n)$ versus $R(n,n)$ when $G,H$ are complete graphs and $c=2.$

I suppose such questions are much too general to be worth thinking about. Maybe I should just ask:

Question 0. Is $R_\ell(3)=6$? [Oops, see below.]

I guess that's true but the proof might be a bit tedious.


P.P.S. Actually it's quite easy to see that $R_\ell(3)=6=R(3,3),$ i.e., if each edge of $K_5$ is assigned a list of two colours, we can give each edge a colour from its list without creating a monochromatic triangle. Since $R(4,4)=18,$ I guess the following is the smallest nontrivial case:

Question 1. Is $R_\ell(4)=18$?


P.P.P.S. Although it doesn't fit in with my original question (which asked only about lists of size $2$), perhaps a better starting point would be to ask about the list version of the tricolour Ramsey number $R(3,3,3)=17.$ This amounts to asking whether the General Conjecture holds when $c=3$ and $H=K_3$ and $G=K_{16}:$

Question 2. If a list of $3$ different colours is assigned arbitrarily to each edge of the complete graph $K_{16},$ can we colour each edge with a colour from its assigned list, without creating a monochromatic triangle?

$\endgroup$
  • 2
    $\begingroup$ Is there anything stopping me from never using a colour more than once? $\endgroup$ – Ben Barber Apr 26 '18 at 10:52
  • 1
    $\begingroup$ Is there any reason to ever include a third color in any of the lists assigned to the edges? If we want to ensure a monochromatic $K_m$, why wouldn't the best strategy be to involve as few colors as possible? $\endgroup$ – Michael Engen Apr 26 '18 at 12:22
  • 3
    $\begingroup$ It is conjectured that, for edge colouring, list chromatic numbers and regular chromatic numbers always agree (and this known for at least edge colourings of bipartite graphs). This might be (weak) evidence that list Ramsey numbers also agree with regular Ramsey numbers. $\endgroup$ – Thomas Bloom Apr 26 '18 at 19:59
  • 3
    $\begingroup$ When I saw the question title "list Ramsey numbers" I expected the answer to be "1, 2, 6, 18, (subsequent terms unknown)"... $\endgroup$ – Adam P. Goucher Apr 26 '18 at 22:20
  • 2
    $\begingroup$ A different notion of list Ramsey number has been considered by Bustamante and Stein. See here: arxiv.org/abs/1510.05190. $\endgroup$ – David Conlon Apr 27 '18 at 12:57

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.