Максимальное несравнимое подмножество целочисленного куба.

[Reyn]

Доброго времени суток.

Есть $n$-мерный целочисленный куб
$C=\{0,1, \ldots K\}^n$
На нём можно ввести частичный порядок. Для $x',x''\in C$
$x'\le x'' $, если $x'_i\le x_i'', i=0,1,\ldots n$.
Покоординатное сравнение. Если удалось сравнить, то элементы сравнимы. Иначе они несравнимы.
Например, в для случая $K=1, n=2 $
$ (0,1) (1,1) $ сравнимы, $ (0,1) (1,0) $ несравнимы.

Чем больше размерность, те больше подмножества в которых все элементы будут попарно несравнимы, можно выделить ($K=1, n=3 $ - $ (1,0,0) (0,1,0) (0,0,1) $ ).

Мне нужно понять какая асимптотически может быть мощность у таких подмножеств.

В случае $K=1$ все просто. Берём элементы, сумма координат которых $ n/2$ (с точностью до целой части). Они несравнимы. Их $C_n^{n/2}$. По Стирлингу оцениваем, получаем, что их порядка $2^n$ (не совсем это аккуратно, но для меня всякие корни и прочее не играют роль в данном случае, важно, что число несравнимых элементов по порядку растёт так же как и число всех элементов в $C$).

Понятно, что если для произвольного $K$ взять элементы из $C$ для которых сумма координат будет $Kn/2$ (опять-таки с точностью до целой части), то они будут несравнимы.
Есть подозрение, что это и есть максимальное подмножество, и что его мощность будет порядка $(K+1)^n$.
Так ли это?

С детства сохранилось воспоминание, что задача о числе счастливых билетов решалась с помощью чего-то подобного. Из-за этого, есть очень сильное подозрение, что то, что меня интересует хорошо известный факт. Где об это могло бы быть написано?

Подмножество куба, для элементов которого сумма координат $Kn/2$.
У меня есть смутные ощущения, что данный объект называет то ли медианой, то ли диагональю. У него есть какое-то правильное название в целочисленном случае?


Заранее спасибо за помощь.

[AD]

Антицепь называется. И вроде как, да, несложно доказывалось где-то, что самая большая из них - "посерединке", то есть тупо берем весь средний слой. То есть ответ $C_n^{[n/2]}$.

-- Ср окт 28, 2009 17:59:36 --

Теорема Шпернера вроде называется.

[RIP]

AD в сообщении #255976 писал(а):

Антицепь называется. И вроде как, да, несложно доказывалось где-то, что самая большая из них - "посерединке", то есть тупо берем весь средний слой. То есть ответ $C_n^{[n/2]}$.

-- Ср окт 28, 2009 17:59:36 --

Теорема Шпернера вроде называется.

Это для $K=1$. Если взять стандартное доказательство через неравенство Любеля--Мешалкина--Ямамото, то для произвольного $K$ неравенство примет вид

$$\sum_{x\in A}\prod_{\nu=0}^K\binom K\nu^{x(\nu)}\cdot\binom{Kn}{\sum_{\nu=0}^K\nu x(\nu)}^{-1}\le1.$$

Здесь $A$ --- это антицепь, $x(\nu)$ --- количество $x_i$, равных $\nu$ ($0\le\nu\le K$).
При $K=1$ ответ получаем мгновенно, а вот при $K>1$ как-то не очень.

[Reyn]

Насколько я понимаю, из неравенства Любеля--Мешалкина--Ямамото можно получить только оценку сверху.
Теорема Шпернера доказывается туда же.
А мне нужно скорее снизу.

Для произвольного $K$ справедлива оценка
$C_n^{n/2} \le|A|\le (K+1)^n$
Где $A$ - это нужная мне антицепь.
Правое тривиальное, левое следует из случая $K=1$.
Вопрос в том, насколько можно усилить левое при $K>1$.
Может быть, через ЛМЯ можно попытаться доказать, что усилить нельзя. Но что-то как-то в это с трудом верится. Если брать антицепь, где сумма компонент элементов равна $Kn/2$, то очевидно, что при $n>2K$ их там как минимум в $K/2$ раз больше чем $C_n^{n/2}$. То есть $K$ так или иначе должно войти в оценку.


PS спасибо за просвещение на счёт антицепи =)

[RIP]

Чё-то я ступил. Хотел точный ответ получить. А оценка снизу, очевидно, тоже $(K+1)^n\cdot n^{O(1)}$. Достаточно взять наборы, в которых кол-ва единиц, двоек,..., $K$-к равны по $\lfloor n/(K+1)\rfloor$. Таких наборов

$$\frac{n!}{\lfloor n/(K+1)\rfloor!^K(n-K\lfloor n/(K+1)\rfloor)!}=(K+1)^n\cdot n^{O(1)}.$$

[Reyn]

Супер.
Премного благодарен.

[AD]

RIP в сообщении #255986 писал(а):

то для $K=1$.

Ой, да, не заметил, что еще $K$ есть ...