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

23

Dla A[n] Oznaczmy przez aiith najmniejszy element A .

Na dwa k -elementowe zestawów, A,B[n] , mówimy, że B jeśli jab I dla każdego I .ABaibii

k -uniform hipergraf H[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,BHABBAk(nk)+1

Mówimy, że hipergraph 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!

domotorp
źródło
2
Właściwość B jest częściej nazywana 2-kolorowalnością.
Colin McQuillan,
1
@Colin McQuillan: Też tak myślałem, ponieważ nigdy nie słyszałem nazwy „Właściwość B”. Wydaje się jednak, że „Właściwość B” jest popularną nazwą w literaturze. en.wikipedia.org/wiki/Property_B
Tsuyoshi Ito
2
Poprawiono mnie. Usunąłem również złą odpowiedź.
Colin McQuillan,

Odpowiedzi:

13

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 4 = c 5 , wówczas wszystkie 1, 2 i 3 muszą mieć kolor przeciwny do c 4 , ale dałoby to monochromatyczny efekt hipergezy (123). Dlatego musi być tak, że c 4c 5 . Podobnie,

  • c 3c 4 przez porównanie trzech hiperwertów (345), (346), (347) i zauważenie hipergezy (567).
  • c 6c 7 przez porównanie trzech hiperwertów (367), (467), (567) i zauważenie hipergezy (345).
  • c 5c 6 przez porównanie trzech hiperwertów (567), (568), (569) i zauważenie hipergezy (789).

Dlatego mamy c 3c 4c 5c 6c 7 . Ale to implikuje c 3 = c 5 = c 7 , co sprawia, że ​​hipersge (357) jest monochromatyczny. Jest to sprzeczne z założeniem kolorowania 2.

Tsuyoshi Ito
źródło
3
Bardzo ładnie mówiąc, pytający lubi twój dowód. Dzięki za zapisanie tego!
domotorp
1

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

1/22(12)k=2k+1B

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

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

Marc Bury
źródło
2
Masz rację, że jeśli k jest wystarczająco duże w porównaniu do n, to zdanie jest prawdziwe (np. K = n trywialnie). Problem polega na udowodnieniu, że jeśli k jest większe niż jakaś stała bezwzględna, tj. 4, to stwierdzenie jest prawdziwe dla każdego n.
domotorp
Ok, więc po prostu zignoruj ​​odpowiedź :)
Marc Bury