Sind Schaltketten zweifarbig?

23

Für A[n] bezeichnen , indem ai die ith kleinstes Element A .

Für zwei k Elementmengen A,B[n] sagen wir, dass AB wenn aibi für jedes i .

A k -Einheitliche Hypergraphen H[n] ist eine sogenannte shift-Kette , wenn für irgendwelche Hyperkanten, A,BH , haben wir AB oder BA . (Eine Shift-Kette hat also höchstens k(nk)+1 Hyperedges.)

Wir sagen, dass ein Hypergraph H zweifarbig ist (oder dass er die Eigenschaft B hat), wenn wir seine Eckpunkte mit zwei Farben so färben können, dass kein Hyperedge einfarbig ist.

Stimmt es, dass Schaltketten zweifarbig sind, wenn k groß genug ist?

Bemerkungen. Ich habe dieses Problem zum ersten Mal auf mathoverflow gepostet , aber niemand hat es kommentiert.

Das Problem wurde auf dem 1. Emlektabla-Workshop für einige Teilergebnisse untersucht, siehe die Broschüre .

Die Frage ist motiviert durch die Zerlegung von Mehrfachbedeckungen der Ebene durch Umsetzungen von konvexen Formen, es gibt viele offene Fragen in diesem Bereich. (Weitere Informationen finden Sie in meiner Doktorarbeit .)

Für k=2 gibt es ein triviales Gegenbeispiel: (12), (13), (23).

Ein sehr magisches Gegenbeispiel für k=3 Radoslav Fulek mit einem Computerprogramm:

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

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

Wenn wir zulassen, dass der Hypergraph die Vereinigung von zwei Schaltketten (mit derselben Reihenfolge) ist, dann gibt es ein Gegenbeispiel für k .

Aktualisieren. Ich habe kürzlich gezeigt, dass eine eingeschränktere Version von Schichtketten in diesem Vorabdruck zweifarbig ist .

Dauerprämie! Ich freue mich, jederzeit ein Kopfgeld von 500 für eine Lösung zu vergeben!

domotorp
quelle
2
Eigenschaft B wird häufiger als 2-Färbbarkeit bezeichnet.
Colin McQuillan
1
@Colin McQuillan: Das habe ich mir auch gedacht, weil ich den Namen „Property B“ noch nie gehört hatte. Es scheint jedoch, dass "Eigenschaft B" ein gebräuchlicher Name in der Literatur ist. en.wikipedia.org/wiki/Property_B
Tsuyoshi Ito
2
Ich stehe korrigiert. Ich habe auch meine falsche Antwort gelöscht.
Colin McQuillan

Antworten:

13

Dies ist keine Antwort. Was folgt, ist ein einfacher Beweis, dass die Konstruktion für k = 3 tatsächlich ein Gegenbeispiel ist. Ich denke, dass der Fragesteller diesen Beweis kennt, aber ich werde ihn trotzdem posten, da der Beweis schön ist und dies nützlich sein könnte, wenn Leute den Fall eines größeren k betrachten .

Es ist leicht zu überprüfen, ob es sich um eine Schaltkette handelt. Lassen Sie uns zeigen, dass es keine Eigenschaft B hat.

Tatsächlich ist der Unterhypergraph {(123), (145), (245), (345), (346), (347), (357), (367), (467), (567), (568), (569), (789)} erfüllen die Eigenschaft B bereits nicht. Um dies zu sehen, nehmen wir an, dass dieser Hypergraph eine 2-Färbung hat und c i die Farbe des Scheitelpunkts i ist . Schauen Sie sich drei Hyperecken an (145), (245), (345). Wenn c 4 = c 5 , müssen alle von 1, 2 und 3 die entgegengesetzte Farbe zu c 4 haben , aber dies würde eine monochromatische Hyperecke ergeben (123). Daher muss c 4c 5 sein . Ähnlich,

  • c 3c 4 durch Vergleichen der drei Hyperecken (345), (346), (347) und Feststellen einer Hyperecke (567).
  • c 6c 7 durch Vergleichen der drei Hyperecken (367), (467), (567) und Erkennen einer Hyperecke (345).
  • c 5c 6 durch Vergleichen der drei Hyperecken (567), (568), (569) und Erkennen einer Hyperecke (789).

Wir haben also c 3c 4c 5c 6c 7 . Dies impliziert jedoch, dass c 3 = c 5 = c 7 ist , wodurch das Hyperedge (357) monochromatisch wird. Dies widerspricht der Annahme der Zweifarbigkeit.

Tsuyoshi Ito
quelle
3
Sehr schön ausgedrückt, der Fragesteller mag Ihren Beweis. Danke, dass du es aufgeschrieben hast!
Domotorp
1

Vielleicht fehlt mir etwas, aber ich denke, es gibt eine gute Untergrenze für die probabilistische Methode:

Wenn Sie jede Ecke Farbe indepedently mit einer Wahrscheinlichkeit von für jede Farbe dann einen einfarbigen Rand mit einer Wahrscheinlichkeit von 2 ( 11/22(12)k=2k+1B

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

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

Marc Bury
quelle
2
Sie haben Recht, wenn k im Vergleich zu n groß genug ist, dann ist die Aussage wahr (z. B. k = n trivial). Das Problem besteht darin, zu beweisen, dass wenn k größer ist als eine absolute Konstante, dh 4, dann gilt die Aussage für jedes n.
Domotorp
Ok, dann ignoriere einfach die Antwort :)
Marc Bury