Расширения теоремы Рамсея: одноцветные, но разнообразные

9

В качестве продолжения моего предыдущего вопроса , который был разрешен Сянь-Чжи Чангом, приведу еще одну попытку найти соответствующее обобщение теоремы Рамсея. (Вам не нужно читать предыдущий вопрос; этот пост является самостоятельным.)


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

Позволять B={1,2,...,N}, Для каждогоk-подмножество SBназначьте цвет f(S){0,1},

Определения:

  • XBявляется монохроматическим, еслиf(S)=f(S) для всех k-подмножеств SX а также SX,
  • XBэто разнообразно , еслиX={x1,x2,...,xn} такой, что xi<xi+1 а также xixi+1 mod dдля всех .i

Например, если , то разнообразны, а - нет. Обратите внимание, что подмножество разнообразного набора не обязательно разнообразно.d=10{12,15,23,32,39}{12,15,25,32,39}

Теперь теорема Рэмси говорит , что независимо от того , как мы выбираем , есть монохромные -подмножество . И , очевидно , это тривиально , чтобы найти разнообразный -подмножество .fnXBnXB

Вопрос: есть ли всегда разнообразны и монохромные -подмножества ?nXB


Изменить: Сянь-Чи Чанг показывает, что утверждение является ложным для простого , но как насчет составного ? В моих приложениях у меня будет большая свобода выбора точных значений , если я могу сделать их произвольно большими. Они могут быть степенями простых чисел, произведений простых чисел или чего-либо еще, что необходимо для того, чтобы сделать утверждение верным.dddkn

Юкка Суомела
источник

Ответы:

7

Сначала я должен сказать: эта проблема действительно интересна! И здесь я кратко опишу, почему мои предыдущие подходы потерпели неудачу, как было предложено в этом мета-посте о неправильных ответах.

  • Моя первая попытка была попытаться построить раскраску, связанную с суммой k-подмножества, которая делает все n-подмножества немонохроматическими. Лемма 1 все еще доступна; но лемма 2 была неверной, поскольку мы наблюдали, что если k и d связаны между собой простыми является n-подмножество в модуле d, предложенное @Jukka.{1,3,1,3,}

  • Вторая попытка была доказательством теоремы; подсчитывая соотношение разнообразных и монохроматических -подмножеств, мы надеемся, что число монохроматических превзойдет число разнородных. Но в моих вычислениях есть ошибка, наблюдаемая @domotorp: соотношение не-разности не приближается к нулю; оно сходится примерно к , что явно больше, чем .nn/dR(n,n;k)n

  • Третий возвращается к первому методу и показывает, что для сверхслабого набора параметров ( и ) теорема неверна. Мы использовали известную лемму в аддитивной комбинаторике: теорема EGZ.n>k+d1dk


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

Разнообразный n-набор содержит по меньшей мере одно k-подмножество с по меньшей мере «переключениями между классами модов»; точно, пусть - разнообразное n-множество, и пусть , переключатель определен, если и находятся в разных мод-д классы. У нас есть k-1 переключатели для .k1X=x1,,xnS=x1,,xkxixi+1S

Пусть k-подмножество будет красным, если имеет не более k-2 переключателей; в противном случае это синий . По предыдущему абзацу мы уже имели синий, теперь доказано , что при , есть красный в любом п-множество . Так как , есть два числа в одном классе mod-d и ; и поскольку , в есть по меньшей мере k-2 элементов с или . И мы можем построить k-подмножество сSSn>k+d+1SXn>dxi,xjjid1n>k+d+1xkXk<ik>jSxiрядом с , который переключается только не более k-2 раз. Таким образом, является красным k-подмножеством.xjS

Сянь-Чжи Чан 張顯 之
источник
1
Я задал вопрос по МО для запроса литературы в обобщенном EHC по циклическим группам.
Сянь-Чи Чанг 之 之
Спасибо, это было поучительно, но я не уверен, можно ли его продлить, чтобы показать, что утверждение является ложным для составного . Например, если и нечетно, то разнообразный может состоять из элементов, которые поочередно или mod , и никакое подмножество не равно нулю mod ? dd=4kX13dkd
Юкка Суомела
Относительно реальной проблемы: все это связано с доказательством утверждений вида «не существует детерминированного распределенного алгоритма, который бы решал эту проблему с графом меньше, чем столько раундов связи». Теория Рамсея была успешно применена во многих случаях; см., например, лекцию 4 здесь . Но иногда мне нужно что-то более сильное, чем «простые» монохромные подмножества. Это длинная история, и на данный момент все это смущающе расплывчато, но если это приведет к чему-то конкретному, я обязательно напишу здесь подробное объяснение!
Юкка Суомела
@Jukka: Спасибо, что любезно поделились своими идеями, я надеюсь, что вы скоро найдете что-то действительно хорошее! Что касается случая, когда d является составным, у меня есть несколько идей, чтобы справиться с ними, но это все еще немного грязно, я подумаю еще несколько часов, прежде чем записывать их, на случай, если идеи не развалится. ..
Сянь-Чи Чанг 之 之
@Jukka: я обнаружил странную ошибку в своем доказательстве. В лемме 3 не следует считать, что меньше, таким образом, меньше, чем ? Иначе невозможно, чтобы все отличались друг от друга. Я постараюсь исправить ошибку. Но в настоящее время доказательство не работает ...k|X|dxi
Сянь-Чжи Чанг 之 之
6

Возможно, я неправильно понял ваш вопрос, но если нет, я думаю, что это неверно. Окрасьте k-множества, все члены которых совпадают по модулю d, красным, остальные k-множества синим. Если n> kd, то любой n-набор должен содержать k-набор, все члены которого являются конгруэнтными по модулю d и, следовательно, красным. С другой стороны, если k-множество содержит два последовательных элемента разнородного n-множества, то оно синего цвета.

domotorp
источник
1
Это умно! И нам нужен только . Ваш ответ исключает почти все случаи ... Теперь единственными возможностями являются , которых не так уж много. n>(k1)dn(k1)d
Сянь-Чи Чанг 之 之