Теорема Рамсея для коллекций множеств

13

При изучении различных методов доказательства нижних границ для распределенных алгоритмов мне пришло в голову, что следующий вариант теоремы Рэмси может найти применение - если это окажется правдой.


Параметры: , K , n заданы, а затем N выбирается достаточно большим. Терминология: m- подмножество - это подмножество размера m .kKnNmm

  • Пусть = { 1 , 2 , . , , , N } .A={1,2,...,N}
  • Пусть состоит из всех К -подмножествам А .BkA
  • Пусть состоит из всех K -подмножествах B .CKB
  • Назначение окраски из C .f:C{0,1}C

Теперь теорема Рамсея (версия с гиперграфом) гласит, что независимо от того, как мы выбираем , существует одноцветное n -подмножество B в B : все K -подмножества B имеют одинаковый цвет.f nBBKB

Я хотел бы пойти еще дальше и найти монохроматическое подмножество A в A : если B B состоит из всех k -подмножеств A , то все K -подмножества B имеют одинаковый цвет.nAABBkAKB


Это правда или ложь? У него есть имя? Вы знаете какие-либо ссылки?

Если это неверно по каким-то тривиальным причинам, есть ли более слабый вариант, напоминающий это утверждение?

Юкка Суомела
источник
1
Не ответ, но краткий справочник в случае, если это поможет: это, кажется, немного связано с -обнаруживающей проблемой проектирования, когда вы хотите (и можете получить) небольшую коллекцию s -подмножеств n, которая содержит все r -подмножества n при r < s < n . (r,s,n)snrnr<s<n
Лев Рейзин
Теперь есть дополнительный вопрос: cstheory.stackexchange.com/questions/3795
Юкка Суомела,

Ответы:

13

Замечено, что вопрос нетривиален только тогда, когда k, K оба больше 1; для случая k = 1 или K = 1 это просто нормальная теорема Рамсея, которая верна для всех n. Кроме того, мы имеем дело только с тем, что > K, в противном случае теорема верна, поскольку существует не более одного ( n(nk) -подмножество B ', построенное n-подмножеством A' в A.(nk)


Сначала докажем, что теорема неверна для всех k> 1, K> 1 и любого n удовлетворяет > K>((nk).(n1k)

Чтобы построить контрпример, для любых больших N и A = [N], мы должны построить функцию раскраски f такую, что для всех n-подмножеств A 'в A, если B' состоит из всех k-подмножеств A ' некоторые из K-подмножеств B 'имеют разные цвета. Здесь мы имеем следующее наблюдение:

Наблюдение 1. В условиях, когда k, K> 1 и > K>((nk) любое K-подмножество B является подмножеством не более одного B ', построенного из n-подмножества A' в A.(n1k)

Наблюдение можно легко представить, представив в виде гиперграфа. Пусть A - узлы графа G, n-подмножество A 'из A - это множество узлов полного n-подграфа в G. B' - это множество k-гиперграней в полном подграфе (2-гипередж является нормальное ребро), и K-подмножества B '- все комбинации (существуют всего, где | B '| = ( п(|B|K) ) из K k-гиперферг. Наблюдение гласит: любой K-кортеж гиперэджей в G принадлежит не более одного полного n-подграфа, что очевидно для ( n(nk) > K>( n - 1(nk), поскольку любые два полных n-подграфа пересекаются не более чем в n-1 узлах, причем не более(n-1)(n1k)гиперчувствительность.(n1k)

Тогда мы можем назначить разные цвета в K-подмножествах C 'конкретного B', построенного из n-подмножества A ', так как любой элемент в C' не будет встречаться как другое K-подмножество B '', созданного из n-подмножеств A ''. Для любого K-подмножества B, не построенного никаким n-подмножеством A, мы назначаем ему случайный цвет. Теперь у нас есть функция раскраски f, обладающая тем свойством, что ни один B ', построенный из n-подмножеств A, не является монохроматическим, то есть некоторые из K-подмножеств B' имеют разные цвета.


Далее мы покажем, что теорема также неверна для всех k> 1, K> 1 и любого n удовлетворяет > K. Здесь единственная разница состоит в том, что n может быть выбрано настолько большим, что K>(n-1(nk)это неправда. Но с помощью другого простого наблюдения:(n1k)

Наблюдение 2. Если некоторая B ', построенная n-подмножеством A' A, является монохроматической, то каждый B '', построенный n'-подмножеством A '' A 'для n' <n, также является монохроматическим.

Следовательно, мы можем предположить, что теорема справедлива для больших n, применить второе наблюдение и заключить противоречие в первом случае, установив n 'удовлетворяет > K>( n -1(nk); такое n 'должно существовать благодаря тому, что(n(n1k)> K и K>(k(nk)(kk) n 'должно лежать между n и k + 1.

Сянь-Чжи Чан 張顯 之
источник
Отлично, такой простой контрпример, большое спасибо! Интересно, можно ли распространить вашу идею на произвольную?К,К, Например, обязательно ли это также, если1«К«К или 1«К«К?
Юкка Суомела
Да, это также неверно почти во всех случаях. Я отредактирую ответ.
Сянь-Чи Чанг 之 之