2014 dxdy logo

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

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




 
 системы общих представителей (Комбинаторика). Где прочитать?
Сообщение18.01.2014, 16:08 
Доброго времени суток.
В комбинаторике есть такие утверждения про оценки минимальной мощности системы общих представителей:
если есть множество из $n$ элементов, и рассматриваются системы из $s$ $k$-элементных его подмножеств, то минимальная мощность системы общих представителей для этого случая оценивается сверху величиной
$$
\max\left\{\frac{n}{k},\frac{n}{k}\ln\frac{sk}{n}\right\} + \frac{n}{k} + 1;
$$
также для $n\geqslant 32,$ $k \leqslant n/32$ и $4\leqslant \ln\frac{sk}{n} \leqslant k$ существует система подмножеств, для которой любая система общих представителей имеет мощность как минимум
$$
\frac{1}{32}\frac{n}{k}\ln\frac{sk}{n}.
$$
Подскажите, в какой книжке можно прочитать их с доказательством? В книге Холла такого нет. Кто автор этих утверждений, тоже интересно...
(сам нашел их у себя в старых лекционных записях, доказательства тоже там есть, но интересует именно книжка)

-- Сб янв 18, 2014 16:40:20 --

Впрочем нашел в статье Райгородского, оригинал.
Видимо, ответ получен. Наверное, в классических книжках нет, хотя статья 1999 года и может попало в какой-нибудь учебник.

 
 
 [ 1 сообщение ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group