La diagonal de Ramsey número $R(n,n)$ es el mínimo número de $m$ para que el siguiente se tiene: en cualquier borde de la coloración del grafo completo $K_m$ en el que cada borde es de color azul o rojo, hay un monocromático $K_n.$
La lista de Ramsey número (mi nombre) $R_\ell(n)$ es el mínimo número de $m$ para que el siguiente se tiene: podemos asignar a cada arista del grafo completo $K_m$ una lista de diferentes colores, de manera que, en cualquier borde de la coloración de las $K_m$ donde cada borde recibe un color de su lista, hay un monocromática $K_n.$
Esta definición es lo que tenemos si consideramos que la diagonal de los casos de Ramsey del teorema de afirmaciones acerca de la cromática números de ciertos hypergraphs y, a continuación, reemplazar cromática números de la lista cromática números.
Claramente $R_\ell(n)\le R(n,n),$ ya que puede simplemente asignar a la lista de $\{\text{blue, red}\}$ a cada borde.
Por otro lado, el probabilístico límite inferior funciona de la misma para $R_\ell(n)$ como $R(n,n),$ así tenemos $R_\ell(n)\ge2^{n/2}.$
Preguntas. Se han dicho cosas que ha estudiado? ¿Alguna vez sucede que $R_\ell(n)\lt R(n,n)$?
Por supuesto que podemos definir de forma análoga variantes de la (diagonal) multicolor y hypergraph Ramsey números, pero tal vez el de arriba es suficiente locura para el día de hoy.
P. S. En un comentario de Thomas Bloom trajo hasta la lista de la coloración conjetura, que dice que la lista de borde cromática número de cualquier gráfico es igual a la ordinaria borde cromática número. Aquí es común que la generalización de la lista de coloración conjetura (para gráficas simples) y la conjetura de que $R_\ell(n)=R(n,n)$:
Conjetura General. Para cualquier simple grafos finitos $G$ e $H$ y cualquier $c\in\mathbb N$ las siguientes afirmaciones son equivalentes:
(a) cualquier borde-la coloración de las $G$ con $c$ colores contiene una copia monocromática de $H$;
(b) podemos asignar a cada borde de $G$ una lista de $c$ distintos colores, de modo que, en cualquier borde de la coloración de las $G$ donde cada borde recibe un color de su lista, hay un monocromática copia de $H.$
Esto se reduce a la lista de coloración conjetura (para gráficas simples) cuando $H=K_{1,2},$ y se reduce a mi pregunta sobre el $R_\ell(n)$ versus $R(n,n)$ cuando $G,H$ son completos gráficos y $c=2.$
Supongo que estas preguntas son demasiado generales para ser vale la pena pensar. Tal vez debería preguntar:
Pregunta 0. Es $R_\ell(3)=6$? [Uy, ver más abajo.]
Supongo que eso es cierto, pero la prueba puede ser un poco tedioso.
P. P. S. en Realidad, es bastante fácil ver que $R_\ell(3)=6=R(3,3),$ es decir, si cada borde de $K_5$ se asigna una lista de dos colores, se puede dar a cada borde de un color de la lista sin necesidad de crear un monocromático triángulo. Desde $R(4,4)=18,$ supongo que el siguiente es el más pequeño trivial caso:
Pregunta 1. Es $R_\ell(4)=18$?
P. P. P. S. a Pesar de que no se adapten a mi pregunta original (en la que pidió a sólo acerca de las listas de tamaño $2$), quizás un mejor punto de partida podría ser la pregunta acerca de la lista de la versión de la tricolor Ramsey número $R(3,3,3)=17.$ Esto equivale a preguntar si la Conjetura General tiene al $c=3$ e $H=K_3$ e $G=K_{16}:$
Pregunta 2. Si una lista de $3$ diferentes colores se asigna arbitrariamente a cada arista del grafo completo $K_{16},$ podemos color de cada borde con un color de su lista, sin la creación de un monocromático triángulo?
