Цепочки переключения двухцветные?

23

Для A[n] обозначим через ai в ith наименьший элемент A .

Для двух k -элементных множеств A,B[n] мы говорим, что AВ если aibi для каждого i .

k -равномерной Гиперграф H[n] , называется сдвигом цепью , если для любых гиперреберов, , B H , мы имеем B или B . (Таким образом, цепочка сдвигов имеет не более k ( n - k ) + 1 гиперферм.)A,BHABBAk(nk)+1

Мы говорим, что гиперграф H является двухцветным (или что он обладает свойством B), если мы можем раскрасить его вершины двумя цветами, чтобы ни один гиперэксид не был монохроматическим.

Верно ли, что сдвиговые цепочки двухцветны, если k достаточно велико?

Замечания. Я впервые опубликовал эту проблему на mathoverflow , но никто не прокомментировал ее.

Проблема была исследована на 1-ом семинаре Эмлектабла для получения некоторых частичных результатов, см. Буклет .

Вопрос мотивирован разложением множества покрытий плоскости переводами выпуклых форм, в этой области много открытых вопросов. (Подробнее см. В моей докторской диссертации .)

Для k=2 существует тривиальный контрпример: (12), (13), (23).

Очень магические контрпример был дан k=3 с помощью Радослава Fulek с помощью компьютерной программы:

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

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

Если мы допустим, чтобы гиперграф был объединением двух цепочек сдвига (с одинаковым порядком), то для любого k существует контрпример .

Обновить. Недавно мне удалось показать, что в этом препринте более ограниченная версия сдвиговых цепочек может быть двухцветной .

Постоянное вознаграждение! Я рад в любое время назначить 500 наград за решение!

domotorp
источник
2
Свойство B чаще называют 2-окрашиваемостью.
Колин МакКийан
1
@Colin McQuillan: я тоже так думал, потому что никогда не слышал названия «Недвижимость B». Тем не менее, кажется, что «Свойство B» является распространенным именем в литературе. ru.wikipedia.org/wiki/Property_B
Цуёси Ито
2
Я стою исправлено. Я также удалил свой неправильный ответ.
Колин МакКиллан

Ответы:

13

Это не ответ. Далее следует простое доказательство того, что конструкция для k = 3 действительно является контрпримером. Я думаю, что спрашивающий знает это доказательство, но я все равно опубликую его, потому что доказательство приятно, и это может быть полезно, когда люди рассматривают случай больших k .

Нетрудно убедиться, что это сдвиговая цепь. Покажем, что у него нет свойства B.

Фактически, подгиперграф {(123), (145), (245), (345), (346), (347), (357), (367), (467), (567), (568), (569), (789)} уже не удовлетворяет свойству B. Чтобы это увидеть, предположим, что этот гиперграф имеет 2-раскраску, и пусть c i будет цветом вершины i . Посмотрите на три гиперграня (145), (245), (345). Если c 4 = c 5 , то все значения 1, 2 и 3 должны быть цвета, противоположного c 4 , но это дало бы монохроматический гиперэкран (123). Следовательно, должно быть так, что c 4c 5 . По аналогии,

  • c 3c 4 , сравнивая три гипергрань (345), (346), (347) и замечая гипергрань (567).
  • c 6c 7 , сравнивая три гипергрань (367), (467), (567) и замечая гипергрань (345).
  • c 5c 6 , сравнивая три гиперэкс (567), (568), (569) и замечая гиперэдж (789).

Следовательно, мы имеем c 3c 4c 5c 6c 7 . Но это означает, что c 3 = c 5 = c 7 , что делает гиперчувствительность (357) монохроматической. Это противоречит предположению о 2-раскраске.

Цуёси Ито
источник
3
Очень хорошо, спрашивающему нравится твое доказательство. Спасибо, что записали это!
domotorp
1

Возможно, я что-то упускаю, но я думаю, что есть вероятная нижняя граница вероятностного метода:

Если цвет каждой вершины indepedently с вероятностью для каждого цвета , то ваш имеют монохроматический край с вероятностью 2 ( 11/22(12)k=2k+1B

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

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

Марк Бери
источник
2
Вы правы, что если k достаточно велико по сравнению с n, то утверждение верно (например, k = n тривиально). Задача состоит в том, чтобы доказать, что если k больше некоторой абсолютной постоянной, то есть 4, то утверждение верно для каждого n.
Домоторп
Хорошо, тогда просто проигнорируйте ответ :)
Марк Бери