Sind Schaltketten zweifarbig?

Für $A\subset [n]$ bezeichnen , indem $a_i$ die $i^{th}$ kleinstes Element $A$ .

Für zwei $k$ Elementmengen $A,B\subset [n]$ sagen wir, dass $A\le B$ wenn $a_i\le b_i$ für jedes $i$ .

A $k$ -Einheitliche Hypergraphen ${\mathcal H}\subset [n]$ ist eine sogenannte shift-Kette , wenn für irgendwelche Hyperkanten, $A, B \in {\mathcal H}$ , haben wir $A\le B$ oder $B\le A$ . (Eine Shift-Kette hat also höchstens $k(n-k)+1$ Hyperedges.)

Wir sagen, dass ein Hypergraph ${\mathcal 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!

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 ₄ = c ₅ , 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 ₄ ≤ c _{5 sein} . Ähnlich,

• c ₃ ≠ c ₄ durch Vergleichen der drei Hyperecken (345), (346), (347) und Feststellen einer Hyperecke (567).
• c ₆ ≠ c ₇ durch Vergleichen der drei Hyperecken (367), (467), (567) und Erkennen einer Hyperecke (345).
• c ₅ ≠ c ₆ durch Vergleichen der drei Hyperecken (567), (568), (569) und Erkennen einer Hyperecke (789).

Wir haben also c ₃ ≤ c ₄ ≤ c ₅ ≤ c ₆ ≤ c ₇ . Dies impliziert jedoch, dass c ₃ = c ₅ = c _{7 ist} , wodurch das Hyperedge (357) monochromatisch wird. Dies widerspricht der Annahme der Zweifarbigkeit.

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 ⋅ ( $1/2$$2 \cdot (\dfrac{1}{2})^k = 2^{-k+1}$$B$

$O(\sqrt{k/\ln(k)} \cdot 2^k)$$k$$B$