Atualização : Agora é conhecido o conjunto de obstruções (ou seja, a "barreira" do NxM entre os tamanhos de grade coloridos e não coloridos) de todos os 4 corantes monocromáticos sem retângulos .
Alguém quer experimentar 5 cores? ;)
A questão a seguir surge da Teoria de Ramsey .
Considere uma cor do gráfico da grade by- . A existe sempre que quatro células da mesma cor são organizadas como os cantos de um retângulo. Por exemplo, e formam um retângulo monocromático se tiverem a mesma cor. Da mesma forma, e formam um retângulo monocromático, se colorido com a mesma cor.n m ( 0 , 0 ) , ( 0 , 1 ) , ( 1 , 1 ) , ( 1 , 0 ) ( 2 , 2 ) , ( 2 , 6 ) , ( 3 , 6 ) , ( 3 , 2 )monochromatic rectangle
Pergunta : Será que não existe um -coloring do -by- gráfico grade que não contém um retângulo monocromática? Nesse caso, forneça a coloração explícita.17 17
Alguns fatos conhecidos:
- 17 4 17 17 16 17 17 17 -by- é -colorable sem um rectângulo monocromática, mas o regime de coloração conhecidas não parecem estender-se ao -by- caso. (Estou omitindo a conhecida cor por- porque provavelmente seria um arenque vermelho para decidir por- ).
- 19 4 por NÃO é de cores sem um retângulo monocromático.
- 18 18 18 -by- e -by- também são casos desconhecidos; uma resposta para isso também seria interessante.
Isenção de responsabilidade: Bill Gasarch tem uma recompensa de US $ 289 (USD) em uma resposta positiva a esta pergunta; você pode contatá-lo através do blog dele. Uma observação sobre etiqueta: vou garantir que ele saiba a fonte de qualquer resposta correta (se houver).
Ele o trouxe novamente à tona durante uma sessão de garupa na Barreiras II, e eu acho interessante, então estou encaminhando a pergunta aqui (sem o seu conhecimento; embora eu duvide que ele se importe).
fonte
Respostas:
Alguns de vocês provavelmente estão cientes disso, mas o problema das cores 17 x 17 foi resolvido por Bernd Steinbach e Christian Posthoff. Veja a publicação do blog de Gasarch aqui .
fonte
Essa não é realmente uma resposta para a pergunta, mas codifiquei o problema de 17 cores 17x17 como um 4-CNF (no formato DIMACS padrão para solucionadores de SAT) e o carreguei aqui . Se alguém tiver acesso a um bom solucionador de SAT (e um supercomputador!), Talvez possamos fazer algum progresso.
Nota: na minha codificação, se o ponto de grade tiver a cor c ∈ { 0 , 1 , 2 , 3 } , a variável ( 17 i + j + 289 c + 1 ) assumirá o valor 1 e 0 caso contrário .( i , j ) c ∈ { 0 , 1 , 2 , 3 } ( 17 i + j + 289 c + 1 ) 1 1 0 0
fonte
Esta também não é uma resposta real. Certamente, o problema aqui é a presença de um número astronômico de simetrias, que enganam até os melhores solucionadores de SAT dos melhores supercomputadores. Tais simetrias mapeiam soluções para soluções e não soluções para não soluções: nesse caso, provavelmente existe um imenso número de quase soluções (ou seja, tarefas que satisfazem todas, exceto uma pequena quantidade de cláusulas), cada uma das quais pode ser obtida por qualquer outra aplicando uma simetria adequada. Portanto, o solucionador perde uma quantidade enorme de tempo tentando cada uma dessas quase soluções, enquanto em certo sentido elas são todas iguais.
A exploração de simetrias (consulte este documento) deve ser uma avenida a ser explorada para atacar essa instância difícil de 17x17 e fazer algum progresso nela. Gostaria de saber se alguém já tentou fazê-lo.
fonte
Mais uma vez, não é uma resposta real, mas, de qualquer forma, aqui estão algumas idéias sobre a adoção de algoritmos de coloração gráfica para esse problema.
Se a família de todos os conjuntos independentes (máximos) tiver uma estrutura suficientemente agradável, também poderá ser possível ajustar o algoritmo do produto de cobertura.
fonte
A grade 21x12 também é de 4 cores, sem retângulos monocromáticos !!!
Veja a última publicação de Bernd Steinbach no blog da Gasarch !
fonte
Este é Bill Bouris. Oi Dan. Estou trabalhando em um programa que procura uma matriz 17x17 adequada que exiba não-4-coloração, de acordo com a Teoria de Ramsey. Eu uso uma matriz posicional que representa todas as conexões entre pontos e fixo a diagonal principal e permito que a linha superior da matriz percorra todas as combinações possíveis de 16choose8; Capto apenas as matrizes que passam em relação aos seguintes critérios ... no-XRRR, no-RXRR, no-RRXR, no-RRRX, no-XBBB, no-BXBB, etc., depois varro a matriz usando o próximo critérios mais fracos ... no-XBRR, noBXRR, no-BBXR, no-BBRX, no-XRBB, no-RXBB, etc., para um total de 32 varreduras até o computador preencher a coloração automaticamente. Percebi que existe um possível candidato para cada 400 matrizes de um total de 12780 e leva 0,95 horas para encontrar o candidato ou 1 para cada 8. 644 segundos. Está chegando, mas não tenho muito tempo para programá-lo ... pois trabalho em período integral. Deveríamos trabalhar juntos ... Eu poderia usar os US $ 289,00!
fonte