Les chaînes de changement sont-elles bicolores?

23

Pour A[n] On note ai la ith plus petit élément de A .

Pour deux ensembles d'éléments k , A,B[n] , nous disons que AB si aibi pour chaque i .

A k -uniform hypergraphe H[n] est appelée une chaîne de changement de vitesse si pour toutes les quantifications, A,BH , on a AB ou BA . (Ainsi, une chaîne de décalage a au plus k(nk)+1 hyper-bords.)

Nous disons qu'un hypergraphe H est bicolore (ou qu'il a la propriété B) si nous pouvons colorer ses sommets avec deux couleurs de telle sorte qu'aucun hyperedge n'est monochromatique.

Est-il vrai que les chaînes de décalage sont bicolores si k est assez grand?

Remarques. J'ai d'abord signalé ce problème sur mathoverflow , mais personne ne l'a commenté.

Le problème a été étudié lors du 1er atelier Emlektabla pour des résultats partiels, voir la brochure .

La question est motivée par la décomposition de multiples revêtements de l'avion par des traductions de formes convexes, il existe de nombreuses questions ouvertes dans ce domaine. (Pour en savoir plus, voir ma thèse de doctorat .)

Pour k=2 il existe un contre-exemple trivial: (12), (13), (23).

Un contre-exemple très magique a été donné pour k=3 par Radoslav Fulek avec un programme informatique:

(123), (124), (125), (135), (145), (245), (345), (346), (347), (357),

(367), (467), (567), (568), (569), (579), (589), (689), (789).

Si nous permettons à l'hypergraphe d'être l'union de deux chaînes de décalage (avec le même ordre), alors il y a un contre-exemple pour tout k .

Mise à jour. J'ai récemment réussi à montrer que des versions plus restreintes des chaînes de décalage sont bicolores dans cette préimpression .

Prime permanente! Je suis heureux d'attribuer une prime de 500 pour une solution à tout moment!

domotorp
la source
2
La propriété B est plus communément appelée 2-colorabilité.
Colin McQuillan
1
@Colin McQuillan: Je le pensais aussi parce que je n'avais jamais entendu le nom «Propriété B». Cependant, il semble que «propriété B» soit un nom courant dans la littérature. en.wikipedia.org/wiki/Property_B
Tsuyoshi Ito
2
Je me suis trompé. J'ai également supprimé ma mauvaise réponse.
Colin McQuillan

Réponses:

13

Ce n'est pas une réponse. Ce qui suit est une simple preuve que la construction pour k = 3 est en effet un contre-exemple. Je pense que le demandeur connaît cette preuve, mais je la posterai quand même parce que la preuve est agréable et cela pourrait être utile lorsque les gens considéreront le cas de k plus grand .

Il est facile de vérifier qu'il s'agit d'une chaîne à décalage. Montrons qu'il n'a pas la propriété B.

En fait, le sous-hypergraphe {(123), (145), (245), (345), (346), (347), (357), (367), (467), (567), (568), (569), (789)} échoue déjà à satisfaire la propriété B. Pour voir cela, supposons que cet hypergraphe a une coloration 2 et soit c i la couleur du sommet i . Regardez trois hyper-bords (145), (245), (345). Si c 4 = c 5 , alors tous les 1, 2 et 3 doivent être de la couleur opposée à c 4 , mais cela donnerait un hyperedge monochromatique (123). Par conséquent, il doit être le cas que c 4c 5 . De même,

  • c 3c 4 en comparant les trois hyper-arêtes (345), (346), (347) et en remarquant une hyper-arête (567).
  • c 6c 7 en comparant les trois hyper-arêtes (367), (467), (567) et en remarquant une hyper-arête (345).
  • c 5c 6 en comparant les trois hyper-arêtes (567), (568), (569) et en remarquant une hyper-arête (789).

Par conséquent, nous avons c 3c 4c 5c 6c 7 . Mais cela implique c 3 = c 5 = c 7 , ce qui rend l'hyperedge (357) monochromatique. Cela contredit l'hypothèse de la 2-coloration.

Tsuyoshi Ito
la source
3
Très bien mis, le demandeur aime votre preuve. Merci de l'avoir écrit!
domotorp
1

Peut-être que je manque quelque chose, mais je pense qu'il y a une bonne limite inférieure avec la méthode probabiliste:

Si vous colorez chaque sommet indepedently avec une probabilité pour chaque couleur, votre un bord monochrome avec une probabilité 2 ( 11/22(12)k=2k+1B

k(nk)+12k1e1.
k=Ω(log(n))nlog(n)ncn

O(k/ln(k)2k)kB

Marc Bury
la source
2
Vous avez raison de dire que si k est assez grand par rapport à n, alors l'énoncé est vrai (par exemple k = n trivialement). Le problème est de prouver que si k est supérieur à une constante absolue, c'est-à-dire 4, alors l'énoncé est vrai pour tout n.
domotorp
Ok, alors ignorez la réponse :)
Marc Bury