Czy łańcuchy zmiany biegów są dwukolorowe?

Dla $A\subset [n]$ Oznaczmy przez $a_i$$i^{th}$ najmniejszy element $A$ .

Na dwa $k$ -elementowe zestawów, $A,B\subset [n]$ , mówimy, że ≤ B jeśli ja ≤ b I dla każdego I .$A\le B$$a_i\le b_i$$i$

$k$ -uniform hipergraf ${\mathcal H}\subset [n]$ jest nazywany zmiana łańcuchu Jeżeli z jakichkolwiek hyperedges, , B ∈ H mamy ≤ B lub B ≤ . (Więc łańcuch zmiany biegów ma najwyżej k ( n - k ) + 1 hipergezy.)$A, B \in {\mathcal H}$$A\le B$$B\le A$$k(n-k)+1$

Mówimy, że hipergraph ${\mathcal H}$ jest dwukolorowy (lub że ma właściwość B), jeśli możemy pokolorować jego wierzchołki dwoma kolorami, tak aby żadna hipergezja nie była monochromatyczna.

Czy to prawda, że ​​łańcuchy zmiany biegów są dwukolorowe, jeśli $k$ jest wystarczająco duże?

Uwagi Po raz pierwszy opublikowałem ten problem na Mathoverflow , ale nikt go nie skomentował.

Problem został zbadany podczas 1. warsztatu Emlektabla pod kątem częściowych wyników, patrz broszura .

Pytanie jest motywowane rozkładem wielu pokryć płaszczyzny przez przekłady wypukłych kształtów, istnieje wiele otwartych pytań w tej dziedzinie. (Aby uzyskać więcej informacji, zobacz moją pracę doktorską .)

Dla $k=2$ istnieje trywialny kontrprzykład: (12), (13), (23).

Bardzo magiczny kontrprzykład podano dla $k=3$ przez Radoslava Fuleka z programem komputerowym:

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

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

Jeśli pozwolimy, aby hypergraph był połączeniem dwóch łańcuchów zmiany biegów (w tej samej kolejności), to istnieje kontrprzykład dla dowolnego $k$ .

Aktualizacja. Niedawno udało mi się pokazać, że bardziej ograniczona wersja łańcuchów zmiany biegów jest dwukolorowa w tym przedruku .

Stała nagroda! W każdej chwili z przyjemnością przyznam 500 nagród za rozwiązanie!

To nie jest odpowiedź. Poniżej znajduje się prosty dowód, że konstrukcja dla k = 3 jest rzeczywiście kontrprzykładem. Myślę, że pytający zna ten dowód, ale i tak go opublikuję, ponieważ dowód jest ładny i może to być przydatne, gdy ludzie rozważą przypadek większego k .

Łatwo jest zweryfikować, że jest to łańcuch zmianowy. Pokażmy, że nie ma właściwości B.

W rzeczywistości subhypergraph {(123), (145), (245), (345), (346), (347), (357), (367), (467), (567), (568), (569), (789)} już nie spełnia właściwości B. aby to zobaczyć, załóżmy, że hipergraf ma 2 barwienia i niech C _i mieć kolor wierzchołka ı . Spójrz na trzy hiperwery (145), (245), (345). Jeśli c ₄ = c ₅ , wówczas wszystkie 1, 2 i 3 muszą mieć kolor przeciwny do c ₄ , ale dałoby to monochromatyczny efekt hipergezy (123). Dlatego musi być tak, że c ₄ ≠ c ₅ . Podobnie,

• c ₃ ≠ c ₄ przez porównanie trzech hiperwertów (345), (346), (347) i zauważenie hipergezy (567).
• c ₆ ≠ c ₇ przez porównanie trzech hiperwertów (367), (467), (567) i zauważenie hipergezy (345).
• c ₅ ≠ c ₆ przez porównanie trzech hiperwertów (567), (568), (569) i zauważenie hipergezy (789).

Dlatego mamy c ₃ ≠ c ₄ ≠ c ₅ ≠ c ₆ ≠ c ₇ . Ale to implikuje c ₃ = c ₅ = c ₇ , co sprawia, że ​​hipersge (357) jest monochromatyczny. Jest to sprzeczne z założeniem kolorowania 2.

Być może coś mi brakuje, ale myślę, że metoda probabilistyczna ma dobrą dolną granicę:

$1/2$$2 \cdot (\dfrac{1}{2})^k = 2^{-k+1}$$B$

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