Видеотека
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Видеотека
Архив
Популярное видео

Поиск
RSS
Новые поступления






Вторая конференция Математических центров России. Секция «Комбинаторика, дискретная геометрия, случайные структуры»
7 ноября 2022 г. 18:10–18:40, г. Москва, Ломоносовский корпус МГУ, аудитория В4, Ломоносовский пр., 27, к. 1
 


Осьминоги в булевом кубе: семейства с малыми попарными пересечениями

Ф. А. Носков
Дополнительные материалы:
Adobe PDF 1.6 Mb

Количество просмотров:
Эта страница:91
Материалы:2

Аннотация: Мы изучаем следующую проблему. Даны семейства $\mathcal{F}_1, \ldots, \mathcal{F}_\ell$ подмножеств множества $\{1, \ldots, n\}$ и мы предполагаем, что для различных $k, k’$ и произвольных $F_1 \in \mathcal{F}_k$, $F_2 \in \mathcal{F}_{k’}$ имеем $|F_1 \cap F_2|\le m$, где $m$ — некоторая константа. Чему равен максимум произведения мощностей этих семейств? Какова структура экстремального примера?
В этой работе мы находим асимптотику этого произведения и некоторый структурный результат при $n$ стремящемся к бесконечности для константного количества семейств и константного $m$, а также получаем аналогичный результат и для чуть более общей задачи, где для каждой пары семейств своё максимальное разрешённое пересечение.
Решив эту задачу, мы даём ответ и на следующий вопрос. Пусть дан равномерный гиперграф, ребра которого раскрашены в $\ell$ цветов. Чему может быть равно произведение числа клик разного цвета?

Дополнительные материалы: НосковФА.pdf (1.6 Mb)
 
  Обратная связь:
 Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024