RUS  ENG
Полная версия
ВИДЕОТЕКА

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


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

Ф. А. Носков

Аннотация: Мы изучаем следующую проблему. Даны семейства $\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$ цветов. Чему может быть равно произведение числа клик разного цвета?


© МИАН, 2024