Grille

37

Mise à jour : L'ensemble des obstructions (c'est-à-dire la "barrière" NxM entre les tailles de grille colorables et non colorables) pour toutes les couleurs 4 monochromes sans rectangle est maintenant connu .

Quelqu'un veut-il essayer 5 couleurs? ;)


La question suivante découle de la théorie de Ramsey .

Considérons une k coloration du graphique de la grille n -by- m . A monochromatic rectangleexiste à chaque fois que quatre cellules de même couleur sont disposées aux coins d'un rectangle. Par exemple, (0,0),(0,1),(1,1), et forment un rectangle monochromatique si elles ont la même couleur. De même, et forment un rectangle monochromatique, s'ils sont colorés avec la même couleur.(1,0)(2,2),(2,6),(3,6),(3,2)

Question : Existe - il un -coloration du -by- graphique de la grille qui ne contient pas un rectangle monochrome? Si oui, fournissez la coloration explicite.41717

Quelques faits connus:

  • 1716 x est tolérable 4 sans rectangle monochromatique, mais le schéma de coloration connu ne semble pas s'étendre au cas 17 x 17 . ( J'oublie la coloration connue de 16- sur- 17, car ce serait très probablement un piège rouge pour décider de 17 -à- 17 .) 17 4171716171717
  • 18 -by-19 n'estPAS 4 tolérable sans un rectangle monochromatique.
  • 17 sur18 et18 sur18 sont également des cas inconnus; une réponse à ces questions serait également intéressante.

Clause de non-responsabilité: Bill Gasarch bénéficie d'une prime de 289 USD en réponse positive à cette question. vous pouvez le joindre via son blog. Une note sur l'étiquette: je m'assurerai qu'il connaisse la source de toute réponse correcte (le cas échéant).

Il a abordé la question de nouveau au cours d'une session extraordinaire à Barriers II, et je le trouve intéressant, alors je vous pose la question ici (à son insu; je doute fort que cela l’ennuierait).

Daniel Apon
la source
11
Je veux juste ajouter quelques références / pointeurs: mis à part les articles de blog [1,2], les mises à jour sur le blog de bit-player [3,4] sont détaillées et perspicaces. Des discussions substantielles ont eu lieu sur tous ces postes. [1]: blog.computationalcomplexity.org/2009/11/… [2]: blog.computationalcomplexity.org/2009/12/… [3]: bit-player.org/2009/the-17x17-challenge [4] : bit-player.org/2009/17-x-17-a-nonprogress-report Remarque: Pas de formatage dans les commentaires? Comment puis-je faire de jolis liens?
Neeldhara
Ce sont d'excellents liens. Merci Neeldhara! :)
Daniel Apon
De même, merci d'avoir posté ceci ici - j'ai suivi les développements à ce sujet pendant un certain temps, et cela devrait raviver l'intérêt pour le problème!
Neeldhara
2
@Moron: Oui, il suffit de considérer les rectangles dont les côtés sont parallèles aux axes. BTW, il existe également un angle de théorie de la complexité à cela: Bill a supposé que, étant donné la coloration partielle k d'une grille de m par n, déterminer si la coloration peut être complétée sans rectangle est NP-complet.
Kurt
2
Le groupe d'automorphisme du problème est large: symétries préservant la solution, en comptant le permutation rangée-colonne, les permutations des couleurs, les permutations des rangées et les permutations des colonnes. Est - il connu combien de sous - ensembles distincts sans rectangle , il y a de la taille 71 , 72 , 73 , . . . ? 2×4!×(17!)2=6.1×103071,72,73,...
mjqxxxx

Réponses:

23

Certains d’entre vous sont probablement au courant, mais le problème de coloration 17 x 17 a été résolu par Bernd Steinbach et Christian Posthoff. Voir le blog de Gasarch ici .

Lev Reyzin
la source
8
De plus, la grille 18x18 est une quadrichromie sans rectangles monochromes ... maintenant, le seul "pavé manquant" est la grille 21x12
Marzio De Biasi
13

Ce n'est pas vraiment une réponse à la question, mais j'ai codé le problème 17x17 4 couleurs en tant que 4-CNF (au format DIMACS standard pour les solveurs SAT) et je l'ai téléchargé ici . Si quelqu'un a accès à un bon solveur SAT (et à un superordinateur!), Nous pourrons peut-être progresser.

Remarque: dans mon codage, si on attribue la couleur c { 0 , 1 , 2 , 3 } à gridpoint , la variable ( 17 i + j + 289 c + 1 ) prend la valeur 1 et 0 sinon .(i,j)c{0,1,2,3}(17i+j+289c+1)10

Lev Reyzin
la source
3
Impressionnant. (J'ai effectivement accès à un supercalculateur.) Numéros d'exécution de l'étape suivante pour estimer le temps d'exécution de cet objet sur une machine spécifique. Qui sait si cela est raisonnable, mais c'est une approche différente que j'avais déjà envisagée. Maintenant, il est temps d'aller trouver cette question récente sur les solveurs SAT pour que je puisse lire ... :)
Daniel Apon le
Il se trouve que le problème auquel je pensais était lié à #SAT. J'ai donc posé une nouvelle question sur les solveurs SAT à l' adresse cstheory.stackexchange.com/questions/1719/…
Daniel Apon le
Super - laissez-moi savoir comment ça se passe!
Lev Reyzin
4
@Lev, juste une mise à jour aléatoire: il semble que le temps d'exécution du 17x17, même en utilisant le meilleur superordinateur possible et un solveur SAT très rapide, reste astronomique. Le côté positif: il semble évident que le super-ordinateur partiel partiel qui fonctionnera (déjà fait à la main par Beth Kupkin chez Rutgers) doit ensuite être trouvé de manière ciblée, c'est-à-dire rechercher le 1-coloriage partiel exact qui fonctionne (2) - des colorations qui fonctionneront à partir de cela, etc. Inconvénient: il n'y a pas de "solution rapide"; ça doit être un projet à long terme avec plusieurs étapes d'exécution d'un superordinateur
Daniel Apon
1
@ Joe, cependant! Voici un "classement" des meilleurs coloris approximatifs actuels: Classement - Il semble que le recuit simulé fonctionne assez bien pour trouver des colorants approximatifs.
Daniel Apon
4

Ce n'est pas une vraie réponse non plus. Le problème ici est certainement la présence d’un nombre astronomique de symétries, qui trompent même les meilleurs solveurs SAT sur les meilleurs supercalculateurs. De telles symétries dessinent des solutions aux solutions et des non-solutions aux non-solutions: il existe probablement dans ce cas un très grand nombre de quasi-solutions (c.-à-d. Des assignations satisfaisant à une faible quantité de clauses), chacune pouvant être obtenue par une autre appliquer une symétrie appropriée. Le solveur perd donc énormément de temps à essayer chacune de ces quasi-solutions, alors qu’elles sont, dans un certain sens, identiques.

L'exploitation des symétries (voir le présent document) devrait être une piste à explorer pour attaquer cette instance difficile de 17x17 et faire quelques progrès. Je me demande si quelqu'un a déjà essayé de le faire.

Giorgio Camerani
la source
Hé, c'est plutôt gentil! :) Je ne l'avais pas vu avant.
Daniel Apon
@ Daniel: de rien! ;-) J'espère que ça aide.
Giorgio Camerani
J'ai utilisé le programme "Shatter" d'Aloul pour plusieurs encodages du problème 17x17 et j'ai mis quelques semaines CPU à quelques résolveurs SAT différents et je n'ai pas eu de chance. Le document cité par Walter est en fait le premier d’une douzaine d’articles ou quelque chose qu’il a écrit sur le sujet. Il pourrait donc y avoir quelque chose qui fera le travail, mais ce n’est pas un fruit à portée de main.
Jay Kominek
3

Encore une fois, ce n'est pas une vraie réponse, mais de toute façon, voici quelques réflexions sur l'adoption d'algorithmes de coloration de graphes pour ce problème.

Disons qu'un ensemble de positions de grille est un ensemble indépendant si l'ensemble I ne contient pas les quatre coins d'un rectangle. Définir un ensemble indépendant maximal de manière évidente. Les revendications suivantes sont équivalentes:II

  1. Lagrille n-à - m peut être colorée avec k couleurs.nmk
  2. Lagrille n - m-m peut être recouverte de k ensembles indépendants.nmk
  3. Lagrille n - m-m peut être recouverte de k ensembles indépendants maximaux.nmk

Ce qui est intéressant, c’est que la couverture avec des ensembles indépendants peut être réalisée en temps utilisant l’algorithme de produit de couverture rapide ( Björklund et al. 2007 ). C’est certainement une amélioration par rapport à l’ algorithme trivial k m n , bien que 2 289 semble encore insurmontable.logk poly(nm)2nmkmn2289

Si la famille de tous les ensembles (maximaux) indépendants a une structure suffisamment jolie, il pourrait également être possible d'affiner l'algorithme du produit couvrant.

Janne H. Korhonen
la source
Comment la revendication 3 équivaut-elle à la revendication 2? L'ensemble indépendant maximal pour 17x17 est d'ailleurs de taille 74, comme le montre l'article de Elizabeth Kupin (pdf) . Il n'y a qu'un seul jeu de ce type, sans compter les permutations des lignes et des colonnes comme distinctes.
Null Set
Je veux dire maximal en ce sens qu’aucun super ensemble proprement dit n’est indépendant, comme il est de coutume en informatique. Maximum est le mot habituellement utilisé pour «taille la plus grande possible».
Janne H. Korhonen,
Dans ce cas, l'ensemble des ensembles indépendants maximaux contient toutes les permutations ligne / colonne de l'ensemble unique de taille 74, et aucun ensemble indépendant de taille 73, car il s'agit tous de sous-ensembles de l'ensemble de taille 74. Je ne sais pas trop ce qu'il y a entre les tailles 67 à 72.
Série nulle
-4

C'est Bill Bouris. Salut Dan Je travaille sur un programme qui recherche une matrice 17x17 appropriée qui ne présente aucune coloration selon la théorie de Ramsey. J'utilise une matrice de positions décrivant toutes les connexions entre les points, puis fixe la diagonale principale et permet à la rangée supérieure de la matrice de parcourir toutes les 16 combinaisons possibles à choisir; Je ne capture que les matrices qui répondent aux critères suivants ... no-XRRR, no-RXRR, no-RRXR, no-RRRX, no-XBBB, no-BXBB, etc., puis je balaye la matrice en utilisant la suivante critère le plus faible ... no-XBRR, noBXRR, no-BBXR, no-BBRX, no-XRBB, no-RXBB, etc., pour un total de 32 balayages jusqu'à ce que l'ordinateur remplisse automatiquement la coloration. J'ai remarqué qu'il y avait un candidat possible sur 400 matrices sur un total de 12780, et qu'il fallait 0,95 heure pour le trouver, soit 1 sur 8. 644 secondes. Ça s'en vient, mais je n'ai pas beaucoup de temps pour le programmer ... car je travaille à plein temps. Nous devrions travailler ensemble ... Je pourrais utiliser les 289,00 $!

William Bouris
la source
Bill Gasarch ne devrait débourser que 128 dollars.
William Bouris
désolé pour cela ... 272/2 ou 136 $
William Bouris
4
Ce n'est pas une réponse à la question. mieux comme commentaire.
Suresh Venkat