2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Семейства подмножеств размеров m и n-m
Сообщение11.08.2018, 17:38 


08/09/13
207
Рассмотрим все подмножества множества $\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 
Заслуженный участник
Аватара пользователя


06/10/08
6094
Эти штуки (с точностью до дополнения множеств) называются 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 
Модератор
Аватара пользователя


11/01/06
5347
База данных для малых размеров множеств есть тут: https://www.ccrwest.org/cover.html

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

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



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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