Teorema de Ramsey para coleções de conjuntos

Ao explorar diferentes técnicas de provar limites inferiores para algoritmos distribuídos, ocorreu-me que a seguinte variante do teorema de Ramsey pode ter aplicações - se isso for verdade.

Parâmetros: , K , n são dados e, em seguida, N é escolhido para ser suficientemente grande. Terminologia: um subconjunto m é um subconjunto de tamanho m .$k$$K$$n$$N$$m$$m$

• Let .$A = \{1,2,...,N\}$
• Deixe- consistem de todos os k -subsets de Uma .$B$$k$$A$
• Vamos consistem em todas as K -subsets de B .$C$$K$$B$
• Atribuir uma coloração de C .$f\colon C \to \{0,1\}$$C$

Agora, o teorema de Ramsey (a versão do hipergrafo) diz que não importa como escolhemos , existe um subconjunto n monocromático B ' de B : todos os subconjuntos K de B ' têm a mesma cor.$f$ $n$$B'$$B$$K$$B'$

Eu gostaria de ir um passo além e encontrar uma monocromática -subset A ' de A : se B ' ⊂ B é composto por todos os k -subsets de A ' , então tudo K -subsets da B ' têm a mesma cor.$n$$A'$$A$$B' \subset B$$k$$A'$$K$$B'$

Isso é verdadeiro ou falso? Isso tem um nome? Você conhece alguma referência?

Se for falso por alguns motivos triviais, existe uma variante mais fraca que se assemelha a essa afirmação?

Observou que a pergunta não é trivial apenas quando k, K é maior que 1; para o caso k = 1 ou K = 1, é apenas o teorema de Ramsey normal, que é verdadeiro para todos os n. Além disso, precisamos lidar apenas com o caso em que > K, caso contrário, o teorema é verdadeiro, pois existe no máximo um (${n \choose k}$ subconjunto de B 'construído por um subconjunto A' de A.${n \choose k}$

Primeiro, provamos que o teorema é falso para todos k> 1, K> 1, e qualquer n satisfaz > K>(n-${n \choose k}$.$({n-1 \atop k})$

Para construir um contra-exemplo, para qualquer grande N e A = [N], temos que construir uma função de coloração f tal que para todo o subconjunto n 'A' de A, se B 'consistir em todos os subconjuntos k de A' , alguns dos subconjuntos K de B 'têm cores diferentes. Aqui temos a seguinte observação:

Observação 1. Nas condições em que k, K> 1 e > K>(n-${n \choose k}$, qualquer subconjunto K de B é um subconjunto de no máximo um B 'construído por um subconjunto A' de A.$({n-1 \atop k})$

A observação pode ser facilmente visualizada representando como hipergrafos. Sejam A nós do gráfico G, um subconjunto n 'A' de A é o conjunto de nós de um subgráfico n completo em G. B 'é o conjunto de hiper-margens no subgrafo completo (uma sub-borda 2 é um borda normal) e subconjuntos K de B 'são todas as combinações (existem no total, onde | B '| = ($({|B'| \atop K})$ ) de K-hyperedges. A observação declara: qualquer tupla K de hipervedades em G pertence a no máximo um sub-gráfico n completo, o que é óbvio para (${n \choose k}$ > K>(n-${n \choose k}$, uma vez que quaisquer dois subgráficos n completos se cruzam no máximo n-1 nós, com no máximo(n-$({n-1 \atop k})$hyperedges.$({n-1 \atop k})$

Em seguida, podemos atribuir cores diferentes dentro do subconjunto K 'de um determinado B' construído por um subconjunto A ', pois qualquer elemento em C' não ocorrerá como outro subconjunto K 'de B' 'construído por um subconjunto N UMA''. Para qualquer subconjunto K de B não construído por nenhum subconjunto n de A, atribuímos cores aleatórias a ele. Agora temos uma função de coloração f, com a propriedade de que nenhum B 'construído pelo subconjunto n de A é monocromático, isto é, alguns dos subconjuntos K de B' têm cores diferentes.

A seguir, mostramos que o teorema também é falso para todos os k> 1, K> 1, e qualquer n satisfaz > K. Aqui a única diferença é n pode ser escolhida tão grande, que K>(n-${n \choose k}$não é verdade. Mas por outra observação simples:$({n-1 \atop k})$

Observação 2. Se algum B 'construído por um subconjunto A' de A é monocromático, todo B '' construído por um subconjunto A '' de A 'para n' <n também é monocromático.

Portanto, podemos assumir que o teorema se mantém no n maior, aplicar a segunda observação e concluir uma contradição no primeiro caso, definindo n 'satisfaz > K>( n ′ -$({n' \atop k})$; tal n 'deve existir pelo fato de que($({n'-1 \atop k})$> K e K>($({n \atop k})$, n 'deve estar entre n e k + 1.$({k \atop k})$