23
$\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 colouring 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$
13
  • 2
    $\begingroup$ Is there anything stopping me from never using a colour more than once? $\endgroup$
    – Ben Barber
    Apr 26, 2018 at 10:52
  • 2
    $\begingroup$ @BenBarber There's nothing stopping you from "never using a colour more than once" but that would be a worst possible strategy. If you're the player who's assigning the lists, your goal is to force the player who's colouring the edges to make a monochromatic thing. Intuitively, it would seem that the best possible strategy would be to assign the same two colours to every edge. However, examples from list colouring theory (bipartite graphs of arbitrarily large list chromatic number) suggest that this intuition may be wrong. $\endgroup$
    – bof
    Apr 26, 2018 at 17:40
  • 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$ Apr 26, 2018 at 19:59
  • 4
    $\begingroup$ When I saw the question title "list Ramsey numbers" I expected the answer to be "1, 2, 6, 18, (subsequent terms unknown)"... $\endgroup$ Apr 26, 2018 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$ Apr 27, 2018 at 12:57

1 Answer 1

12
$\begingroup$

we stumbled upon the same concept in a different way and discovered this topic when looking if someone studied it already.

We have figured out some interesting things, such as:

  • disproving your general conjecture (it is false for matchings),

  • proving it is true for stars (except for very small stars),

  • proving behaviour is very different between the Ramsey numbers even for 3-uniform hypergraphs,

  • obtaining several other results giving various bounds for general (hyper)graphs.

Your original question of whether it is equal for cliques stays open, even for multiple colours.

Here is the link to the paper: https://arxiv.org/abs/1902.07018

$\endgroup$
1
  • $\begingroup$ Thank you very much for this answer. $\endgroup$
    – bof
    Feb 21, 2019 at 12:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.