El teorema de Ramsey para colecciones de conjuntos.

Mientras exploraba diferentes técnicas para probar límites más bajos para algoritmos distribuidos, se me ocurrió que la siguiente variante del teorema de Ramsey podría tener aplicaciones, si resulta ser cierto.

Parámetros: se dan , , , y luego se elige para que sea lo suficientemente grande. Terminología: un subconjunto m es un subconjunto de tamaño m .K n $k$$K$$n$$N$$m$$m$

• Let $A = \{1,2,...,N\}$ .
• Deje $B$ constan de todos los $k$ -subsets de $A$ .
• Deje $C$ consiste completamente de $K$ -subsets de $B$ .
• Asignar una coloración $f\colon C \to \{0,1\}$ de $C$ .

Ahora el teorema de Ramsey (la versión hipergráfica) dice que no importa cómo elijamos $f$ , existe un n -subconjunto B monocromático B ' de B : todos los K- subconjuntos de B ' tienen el mismo color.$n$$B'$$B$$K$$B'$

Me gustaría ir un paso más allá y encontrar un monocromática -subset A ' de A : Si B ' ⊂ B se compone de todos los k -subsets de A ' , entonces todo K -subsets de B ' tienen el mismo color.$n$$A'$$A$$B' \subset B$$k$$A'$$K$$B'$

¿Es esto cierto o falso? Eso tiene un nombre? ¿Conoces alguna referencia?

Si es falso por algunas razones triviales, ¿hay una variante más débil que se parezca a esta afirmación?

Observó que la pregunta no es trivial solo cuando k, K son mayores que 1; para el caso k = 1 o K = 1, es solo el teorema normal de Ramsey, que es cierto para todos los n. Además, solo tenemos que lidiar con el caso de que > K, de lo contrario, el teorema es verdadero ya que hay como máximo uno (${n \choose k}$ -subconjunto de B 'construido por un n-subconjunto A' de A.${n \choose k}$

Primero demostramos que el teorema es falso para todos k> 1, K> 1, y cualquier n satisface > K>(n-${n \choose k}$.$({n-1 \atop k})$

Para construir un contraejemplo, para cualquier N grande y A = [N], tenemos que construir una función de coloración f tal que para todos los n-subconjuntos A 'de A, si B' consiste en todos los k-subconjuntos de A ' , algunos de los subconjuntos K de B 'tienen colores diferentes. Aquí tenemos la siguiente observación:

Observación 1. Bajo las condiciones que k, K> 1 y > K>(n-${n \choose k}$, cualquier subconjunto K de B es un subconjunto de a lo sumo un B 'construido por un subconjunto n A' de A.$({n-1 \atop k})$

La observación puede parecer fácilmente representando como hipergrafías. Sea A los nodos del gráfico G, un n-subconjunto A 'de A es el conjunto de nodos de un n-subgrafo completo en G. B' es el conjunto de k-hiperedges en el subgrafo completo (un 2-hiperedge es un borde normal) y los subconjuntos K de B 'son todas las combinaciones (hay en total, donde | B '| = ($({|B'| \atop K})$ ) de K k-hiperedges. La observación establece: cualquier K-tupla de hiperedges en G pertenece a lo más a una n-subgrafía completa, lo cual es obvio para (${n \choose k}$ > K>(n-${n \choose k}$, dado que cualquiera de los dos n-subgrafos completos se cruzan en la mayoría de los nodos n-1, con a lo sumo(n-$({n-1 \atop k})$hiperedges.$({n-1 \atop k})$

Entonces podemos asignar diferentes colores dentro de los K-subconjuntos C 'de un B' particular construido por un n-subconjunto A ', ya que cualquier elemento en C' no ocurrirá como otro K-subconjunto de B '' construido por un n-subconjunto UN''. Para cualquier subconjunto K de B no construido por ningún subconjunto n de A, le asignamos un color aleatorio. Ahora tenemos una función de coloración f, con la propiedad de que ningún B 'construido por el subconjunto n de A es monocromático, es decir, algunos de los subconjuntos K de B' tienen colores diferentes.

A continuación mostramos que el teorema también es falso para todos los k> 1, K> 1 y cualquier n satisface > K. Aquí la única diferencia es que n puede elegirse tan grande que K>(n-${n \choose k}$no es cierto. Pero por otra simple observación:$({n-1 \atop k})$

Observación 2. Si algunos B 'construidos por un n-subconjunto A' de A son monocromáticos, entonces cada B '' construido por un n'-subconjunto A '' de A 'para n' <n también es monocromático.

Por lo tanto, podemos suponer que el teorema se mantiene en la n más grande, aplicar la segunda observación y concluir una contradicción en el primer caso, al establecer n 'satisface > K>( n ′ -$({n' \atop k})$; tal n 'debe existir por el hecho de que($({n'-1 \atop k})$> K y K>($({n \atop k})$, n 'debe estar entre ny k + 1.$({k \atop k})$