2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Максимальное несравнимое подмножество целочисленного куба.
Сообщение28.10.2009, 14:13 


28/10/09
35
Доброго времени суток.

Есть $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$.
У меня есть смутные ощущения, что данный объект называет то ли медианой, то ли диагональю. У него есть какое-то правильное название в целочисленном случае?


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

 Профиль  
                  
 
 Re: Максимальное несравнимое подмножество целочисленного куба.
Сообщение28.10.2009, 16:54 
Экс-модератор


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

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

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

 Профиль  
                  
 
 Re: Максимальное несравнимое подмножество целочисленного куба.
Сообщение28.10.2009, 17:12 
Заслуженный участник
Аватара пользователя


11/01/06
3839
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$ как-то не очень.

 Профиль  
                  
 
 Re: Максимальное несравнимое подмножество целочисленного куба.
Сообщение28.10.2009, 18:33 


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

Для произвольного $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 спасибо за просвещение на счёт антицепи =)

 Профиль  
                  
 
 Re: Максимальное несравнимое подмножество целочисленного куба.
Сообщение28.10.2009, 19:57 
Заслуженный участник
Аватара пользователя


11/01/06
3839
Чё-то я ступил. Хотел точный ответ получить. А оценка снизу, очевидно, тоже $(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)}.$$

 Профиль  
                  
 
 Re: Максимальное несравнимое подмножество целочисленного куба.
Сообщение28.10.2009, 23:23 


28/10/09
35
Супер.
Премного благодарен.

 Профиль  
                  
 
 Re: Максимальное несравнимое подмножество целочисленного куба.
Сообщение28.10.2009, 23:44 
Экс-модератор


17/06/06
5004
RIP в сообщении #255986 писал(а):
то для $K=1$.
Ой, да, не заметил, что еще $K$ есть ... :oops:

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 7 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: tolstopuz


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group