Extensões do teorema de Ramsey: monocromática, mas diversa

9

Como acompanhamento da minha pergunta anterior , resolvida por Hsien-Chih Chang, aqui está outra tentativa de encontrar uma generalização apropriada do teorema de Ramsey. (Você não precisa ler a pergunta anterior; esta postagem é independente.)


Parâmetros: números inteiros são dados e, em seguida, é escolhido para ser suficientemente grande. Terminologia: um subconjunto é um subconjunto de tamanho .1dknNmm

Seja . Para cada -subset , atribuir uma cor .B={1,2,...,N}kSBf(S){0,1}

Definições:

  • f ( S ) = f ( S ) k S X S XXB é monocromática , se para todos os -subsets e .f(S)=f(S)kSXSX
  • XB é diverso se modo que e para todos i .X={x1,x2,...,xn}xi<xi+1xixi+1 mod di

Por exemplo, se d=10 , então {12,15,23,32,39} é diverso, mas {12,15,25,32,39} não é. Observe que um subconjunto de um conjunto diverso não é necessariamente diverso.

Agora o teorema de Ramsey diz que não importa como nós escolhemos f , há uma monocromática n -subset XB . E, obviamente, é trivial para encontrar uma diversificada n -subset XB .

Pergunta: existe sempre uma diversificada e monocromático n -subset XB ?


Edit: Hsien-Chih Chang mostra que a afirmação é falsa para um primo , mas e o composto ? Nos meus aplicativos, terei muita liberdade na escolha dos valores exatos de , desde que eu possa torná-los arbitrariamente grandes. Eles podem ser poderes de números primos, produtos de números primos ou o que for necessário para tornar a afirmação verdadeira.dddkn

Jukka Suomela
fonte

Respostas:

7

Primeiro eu tenho que dizer: esse problema é realmente interessante !! E aqui descrevo brevemente por que minhas abordagens anteriores falharam, conforme sugerido neste meta post sobre respostas incorretas.

  • Minha primeira tentativa foi tentar construir uma coloração relacionada ao subconjunto do subconjunto k, que torna todos os subconjuntos n não monocromáticos. O lema 1 ainda está disponível; mas o Lema 2 estava errado, observando que se k e d estão relacionados primos, então um subconjunto no módulo d sugerido por @Jukka é um contra-exemplo.{1,3,1,3,}

  • A segunda tentativa foi uma prova do teorema; contando a proporção de conjuntos diversos e monocromáticos , esperamos que o número de conjuntos monocromáticos ultrapasse o número de conjuntos diferentes. Mas existe um erro nos meus cálculos, observado por @domotorp: a proporção de não ser diverso não se aproxima de zero; converge para cerca de , que é claramente maior que .nn/dR(n,n;k)n

  • O terceiro uma volta para o primeiro método, e mostra que, para um conjunto de parâmetros de super-fraco ( e ), o teorema é falsa. Utilizamos um famoso lema na combinatória aditiva: o teorema EGZ.n>k+d1dk


A quarta tentativa é devido à resposta de @domotorp; é inteligente e inspirador, e tentarei modificar sua prova para lidar com todos os parâmetros. Mas o método dele ainda é elegante e eu aprecio totalmente essa abordagem simples.

Um n-conjunto diverso contém pelo menos um subconjunto k com pelo menos "alterna entre classes mod"; precisamente, seja um conjunto n diversificado e deixe , uma opção é definida se e estiverem em diferentes mod-d Aulas. Temos k-1 switches para .k1X=x1,,xnS=x1,,xkxixi+1S

Deixe um subconjunto k- ser vermelho se tem no máximo k-2 interruptores; caso contrário, é azul . Pelo parágrafo anterior, já tínhamos um azul, agora provamos que para , existe um vermelho em qualquer n-definido . Como , existem dois números na mesma classe mod-d e ; e desde que , há pelo menos k-2 elementos em com ou . E pode-se construir um subconjunto k- comSSn>k+d+1SXn>dxi,xjjid1n>k+d+1xkXk<ik>jSxipróximo a , que alterna apenas no máximo k-2 vezes. Assim, é um subconjunto k vermelho.xjS

Hsien-Chih Chang 張顯 之
fonte
11
Fiz uma pergunta sobre MO para o pedido de literaturas em EHC generalizada em grupos cíclicos.
Hsien-Chih Chang,
Obrigado, isso foi esclarecedor, mas não tenho certeza se poderia ser estendido para mostrar que a afirmação é falsa para um composto . Por exemplo, se e é ímpar, então um diverso pode consistir em elementos que são alternadamente ou mod e nenhum subconjunto é zero mod ? dd=4kX13dkd
Jukka Suomela
Com relação ao problema real: Tudo isso está relacionado à comprovação de declarações da forma "não há algoritmo distribuído determinístico que resolva esse problema gráfico em menos do que o número de rodadas de comunicação". A teoria de Ramsey foi aplicada com sucesso em muitos casos; veja, por exemplo, aula 4 aqui . Mas, ocasionalmente, preciso de algo mais forte do que "meros" subconjuntos monocromáticos. É uma história longa, e tudo é embaraçosamente vago neste momento, mas se isso levar a algo concreto, certamente escreverei uma explicação detalhada aqui!
Jukka Suomela
@Jukka: Obrigado por compartilhar suas idéias, espero que você venha com algo realmente bom em breve! Quanto ao caso em que d é composto, tenho algumas idéias para lidar com elas, mas ainda é um pouco confuso, pensarei por mais algumas horas antes de anotá-las, caso as idéias não se desmoronem. ..
Hsien-Chih Chang,
@Jukka: Encontrei um erro estranho na minha prova. No Lema 3, não deve ser considerado menor que, portanto menor que ? Caso contrário, é impossível ter todos os 's distintos. Vou tentar corrigir o erro. Mas atualmente a prova está quebrada ...k|X|dxi
Hsien-Chih Chang ...
6

Eu posso ter entendido mal sua pergunta, mas se não, acho que é falsa. Colora os k-sets cujos membros são todos os módulos congruentes d de vermelho e os outros k-sets de azul. Se n> kd, qualquer conjunto n deve conter um conjunto k cujos membros sejam todos módulo congruente d e, portanto, é vermelho. Por outro lado, se um conjunto k contém dois elementos consecutivos de um conjunto n diverso, então é azul.

domotorp
fonte
11
Isso é inteligente! E nós precisamos apenas de de fato. Sua resposta exclui quase todos os casos ... Agora, as únicas possibilidades são , que não são demais. n>(k1)dn(k1)d
Hsien-Chih Chang,