2014 dxdy logo

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

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




 
 Семейства подмножеств размеров m и n-m
Сообщение11.08.2018, 17:38 
Рассмотрим все подмножества множества $\left\lbrace{1,\dots,n}\right\rbrace$ размеров $m$ и $n-m$ ($m \le \frac{n}{2}$)
Скольких множеств размера $m$ достаточно чтобы любое множество размера $n-m$ содержало хотя бы одно из них в качестве подмножества?

При $m < \sqrt{n}$ оптимальной схемой представляется взять $m+1$ непересекающихся множеств. При $m \ge \sqrt{n}$ я не смог придумать ничего лучше чем разбить $\left\lbrace{1,\dots,n}\right\rbrace$ на $\frac{n}{m}-1$ одинаковых непересекающихся кусков и в каждом взять все его подмножества размера $m$.
Особо почему-то кажется интересным случай $m = \delta N$ при фиксированном $\delta$ и $N \to \infty$. Моя схема даёт $\left({\frac{1}{\delta^{\frac{\delta^2}{(1-\delta)}} {(1-\delta)}^{\delta}}}\right)^{N(1+o(1))}$ при $\delta = \frac{1}{k}$. А можно ли улучшить константу в показателе?

(задачу придумал сам)

 
 
 
 Re: Семейства подмножеств размеров m и n-m
Сообщение11.08.2018, 21:33 
Аватара пользователя
Эти штуки (с точностью до дополнения множеств) называются covering designs. Жадный алгоритм дает $\dfrac{C_n^m}{C_{n - m}^m} (1 + \ln C_{n - m}^m)$

 
 
 
 Re: Семейства подмножеств размеров m и n-m
Сообщение28.08.2018, 21:14 
Аватара пользователя
База данных для малых размеров множеств есть тут: https://www.ccrwest.org/cover.html

 
 
 [ Сообщений: 3 ] 


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