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

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

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

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

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

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

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

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

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

Сначала докажем, что теорема неверна для всех k> 1, K> 1 и любого n удовлетворяет > K>${n \choose k}$.$({n-1 \atop k})$

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

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

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

Тогда мы можем назначить разные цвета в 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-${n \choose k}$это неправда. Но с помощью другого простого наблюдения:$({n-1 \atop k})$

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

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