2025-11-25T13:16:17.951447

On the quadratic 8-edge case of the Brown-Erdős-Sós problem

Pikhurko, Sun
Let $f^{(r)}(n;s,k)$ be the maximum number of edges in an $n$-vertex $r$-uniform hypergraph containing no $k$ edges on at most $s$ vertices. Brown, Erdős and Sós conjectured in 1973 that the limit $\lim_{n\rightarrow \infty}n^{-2}f^{(3)}(n;k+2,k)$ exists for all $k$. Recently, Delcourt and Postle settled the conjecture and their approach was generalised by Shangguan to every uniformity $r\ge 4$: the limit $\lim_{n\rightarrow \infty}n^{-2}f^{(r)}(n;rk-2k+2,k)$ exists for all $r\ge 3$ and $k\ge 2$. The value of the limit is currently known for $k\in \{2,3,4,5,6,7\}$ due to various results authored by Glock, Joos, Kim, Kühn, Lichev, Pikhurko, Rödl and Sun. In this paper we consider the case $k=8$, determining the value of the limit for each $r\ge 4$ and presenting a lower bound for $k=3$ that we conjecture to be sharp.
academic

О квадратичном 8-рёберном случае проблемы Брауна-Эрдёша-Шоша

Основная информация

  • ID статьи: 2506.01739
  • Название: On the quadratic 8-edge case of the Brown-Erdős-Sós problem
  • Авторы: Олег Пихурко, Шумин Сунь (Университет Уорвика)
  • Классификация: math.CO (комбинаторика)
  • Дата публикации: 16 октября 2025 г. (версия 2 на arXiv)
  • Ссылка на статью: https://arxiv.org/abs/2506.01739

Аннотация

В данной работе исследуется квадратичный 8-рёберный случай проблемы Брауна-Эрдёша-Шоша. Пусть f(r)(n;s,k)f^{(r)}(n;s,k) обозначает максимальное число рёбер в rr-однородном гиперграфе на nn вершинах, не содержащем kk рёбер, покрывающих не более ss вершин. Браун, Эрдёш и Шош в 1973 году предположили, что для всех kk существует предел lim⁡n→∞n−2f(3)(n;k+2,k)\lim_{n\rightarrow \infty}n^{-2}f^{(3)}(n;k+2,k). Недавно Делькур и Постл разрешили эту гипотезу, а Шанггуань обобщил результат на все однородности r≥4r\ge 4. В данной работе рассматривается случай k=8k=8, определяется значение предела для каждого r≥4r\ge 4 и приводится нижняя оценка для r=3r=3.

Исследовательский контекст и мотивация

  1. Основная проблема: Проблема Брауна-Эрдёша-Шоша изучает числа Турана для rr-однородных гиперграфов, то есть максимальное число рёбер в гиперграфе на nn вершинах при условии избегания определённых запрещённых подграфов.
  2. Значимость проблемы: Это фундаментальная задача экстремальной комбинаторики, тесно связанная с теорией Рамсея, теорией Турана и другими центральными областями. Решение этой проблемы имеет важное значение для понимания структурных свойств гиперграфов.
  3. Существующий прогресс:
    • Браун, Эрдёш и Шош доказали, что f(r)(n;s,k)=Θ(nt)f^{(r)}(n;s,k) = \Theta(n^t), где t=(rk−s)/(k−1)t = (rk-s)/(k-1)
    • При t=2t=2 (то есть s=rk−2k+2s = rk-2k+2) существование предела π(r,k):=lim⁡n→∞n−2f(r)(n;rk−2k+2,k)\pi(r,k) := \lim_{n\to\infty} n^{-2}f^{(r)}(n;rk-2k+2,k) уже доказано
    • Для k∈{2,3,4,5,6,7}k \in \{2,3,4,5,6,7\} значения пределов известны
  4. Исследовательская мотивация: k=8k=8 является следующей естественной целью исследования, и этот случай демонстрирует новую сложность, особенно в различном поведении при r=3r=3 и r≥4r\ge 4.

Основные вклады

  1. Главная теорема: Для всех r≥4r \geq 4 установлено, что π(r,8)=1r2−r\pi(r,8) = \frac{1}{r^2-r}
  2. Результаты нижних оценок: Доказано, что π(3,8)≥316\pi(3,8) \geq \frac{3}{16}, и высказана гипотеза о точности этой оценки
  3. Методы конструирования: Предоставлены явные конструкции, достигающие нижних оценок, основанные на графах инцидентности проективных плоскостей
  4. Структурный анализ: Глубокий анализ структуры G8(r)G^{(r)}_8-свободных гиперграфов, в частности классификация 2-кластеров
  5. Приложения: Установлены связи с обобщёнными числами Рамсея, получено lim⁡n→∞GR(n,18,146)n2=512\lim_{n\to\infty} \frac{GR(n,18,146)}{n^2} = \frac{5}{12}

Подробное описание методов

Постановка задачи

Исследование асимптотического поведения функции f(r)(n;rk−2k+2,k)f^{(r)}(n; rk-2k+2, k) при k=8k=8, то есть определение значения предела π(r,8)=lim⁡n→∞n−2f(r)(n;8r−14,8)\pi(r,8) = \lim_{n\to\infty} n^{-2}f^{(r)}(n; 8r-14, 8).

Методы конструирования нижних оценок

Базовые конструктивные единицы

  • RR-граф: 3-граф на 5 вершинах с 3 рёбрами, состоящий из ребра abcabc и алмаза {buv,cuv}\{buv, cuv\}
  • Семейства путей: Использование дезаргесовой проективной плоскости для конструирования семейства 2-путей PP, удовлетворяющего условиям разреженности и связности

Метод вероятностного удаления

  1. Начало с графа инцидентности проективной плоскости, конструирование двудольного графа G′G'
  2. Случайный выбор 2-путей с вероятностью (logm)/m1/2(log m)/m^{1/2}
  3. Использование метода вероятностного удаления для удаления путей, образующих плотные конфигурации
  4. Размещение копий RR-графа на каждом 2-пути

Ключевые леммы

Лемма 3.2: Для достаточно больших степеней простых чисел qq существует семейство 2-путей PP, удовлетворяющее:

  • ∣P∣=Ω(m3/2log⁡m)|P| = \Omega(m^{3/2} \log m)
  • Объединение ⋃P∈PP\bigcup_{P\in P} P содержит O(m3/2)O(m^{3/2}) рёбер
  • Объединение не содержит треугольников, 4-циклов и 5-циклов
  • Для любого i∈[8]i \in [8] каждое ii-подмножество вершин содержит не менее i+2i+2 вершин

Методы доказательства верхних оценок

Стратегия объединения

  1. 1-объединение: Разбиение множества рёбер на связные 1-кластеры (фактически деревья)
  2. 2-объединение: Дальнейшее объединение в 2-кластеры через условие {1}∣{2}\{1\}|\{2\}-объединяемости

Структурный анализ

Лемма 4.7: Для любого 2-кластера FF с ∣F∣≥9|F| \geq 9, FF принадлежит одному из следующих семейств:

  • AA: 9-рёберный 2-кластер с комбинацией (5,2,2)(5,2,2)
  • BB: 9-рёберный 2-кластер с комбинацией (1,2,4,2)(1,2,4,2)
  • C1,C2C_1, C_2: 2-кластеры с различными комбинациями
  • E,FE, F: 2-кластеры со специальной структурой
  • SiS_i: (2i+1)(2i+1)-рёберный 2-кластер, состоящий из одного 1-дерева и ii алмазов

Назначение весов

Для r≥5r \geq 5 и r=4r = 4 используются различные весовые функции:

При r≥5r \geq 5: wF(uv)={1если 1∈CF(uv)1/3если 2∈CF(uv) и 1∉CF(uv)0иначеw_F(uv) = \begin{cases} 1 & \text{если } 1 \in C_F(uv) \\ 1/3 & \text{если } 2 \in C_F(uv) \text{ и } 1 \notin C_F(uv) \\ 0 & \text{иначе} \end{cases}

При r=4r = 4: Использование максимума пяти вспомогательных функций hiFh_i^F в качестве веса.

Экспериментальная установка

Данная работа является чисто теоретическим исследованием и не включает вычислительные эксперименты. Все результаты получены посредством строгих математических доказательств.

Верификация доказательств

  • Нижние оценки проверяются явным конструированием
  • Верхние оценки доказываются посредством исчерпывающего анализа случаев и методов назначения весов
  • Все ключевые леммы имеют полные математические доказательства

Результаты исследования

Основные результаты

Теорема 1.1: Для каждого r≥4r \geq 4 имеет место π(r,8)=1r2−r\pi(r,8) = \frac{1}{r^2-r}.

Теорема 1.2: π(3,8)≥316\pi(3,8) \geq \frac{3}{16}.

Гипотеза 1.3: π(3,8)=316\pi(3,8) = \frac{3}{16}.

Сравнение с известными результатами

  • π(r,2)=1r2−r\pi(r,2) = \frac{1}{r^2-r} (Рёдль)
  • π(r,4)=1r2−r\pi(r,4) = \frac{1}{r^2-r} (Глок и др.)
  • π(r,6)=1r2−r\pi(r,6) = \frac{1}{r^2-r} для r≥4r \geq 4 (Глок и др.)
  • π(3,6)=61330\pi(3,6) = \frac{61}{330} (частный случай)

Новые открытия

  1. Пороговое явление: r=4r=4 является минимальной однородностью, при которой π(r,8)=1r2−r\pi(r,8) = \frac{1}{r^2-r}
  2. Структурная сложность: Случай k=8k=8 демонстрирует более сложную структуру 2-кластеров по сравнению с ранее изученными значениями kk
  3. Связь с Рамсеем: Установлены новые связи с обобщёнными числами Рамсея

Связанные работы

Историческое развитие

  1. Браун-Эрдёш-Шош (1973): Постановка исходной гипотезы и базовые оценки
  2. Рёдль (1985): Решение случая k=2k=2
  3. Глок (2019): Решение случая k=3k=3
  4. Делькур-Постл (2024): Доказательство существования предела
  5. Шанггуань (2023): Обобщение на все однородности

Техническое развитие

  • Теория конфликтно-независимых паросочетаний: Ключевая техника, разработанная Делькуром-Постлом и Глоком и др.
  • Метод назначения весов: Техника верхних оценок, развитая на основе работ Глока и др.
  • Вероятностные конструкции: Вероятностный метод, основанный на структурах алгебраической геометрии

Заключение и обсуждение

Основные выводы

  1. Полностью определено значение π(r,8)\pi(r,8) для r≥4r \geq 4
  2. Предоставлены возможно оптимальные оценки для случая r=3r=3
  3. Установлены новые связи с обобщёнными числами Рамсея

Ограничения

  1. Случай r=3r=3: Получена только нижняя оценка, совпадение верхней оценки остаётся открытой проблемой
  2. Сложность конструкции: Конструирование нижней оценки весьма техническое, возможно существование более простых конструкций
  3. Обобщение: Применимость метода к большим значениям kk не ясна

Направления будущих исследований

  1. Доказательство гипотезы π(3,8)=316\pi(3,8) = \frac{3}{16}
  2. Исследование случаев k≥9k \geq 9
  3. Поиск более общих конструкций и техник верхних оценок
  4. Исследование связей с другими экстремальными задачами

Глубокая оценка

Преимущества

  1. Техническая инновация: Разработаны новые методы классификации 2-кластеров и назначения весов
  2. Изящные конструкции: Конструкции, основанные на проективных плоскостях, демонстрируют глубокие геометрические идеи
  3. Полнота: Предоставлено полное решение для r≥4r \geq 4
  4. Ясность изложения: Технические детали хорошо организованы и легко понимаются

Недостатки

  1. Неполнота для r=3r=3: Основная открытая проблема остаётся нерешённой
  2. Специфичность методов: Техники высоко специализированы для k=8k=8, обобщаемость ограничена
  3. Вычислительная сложность: Некоторые доказательства весьма длинны и технически сложны

Влияние

  1. Теоретический вклад: Продвижение исследований проблемы Брауна-Эрдёша-Шоша
  2. Методология: Предоставление новых технических инструментов для аналогичных задач
  3. Прикладная ценность: Связи с теорией Рамсея открывают новые направления исследований

Области применения

Данный метод применим к:

  1. Исследованиям экстремальных задач на гиперграфах
  2. Задачам типа Турана с запрещёнными подграфами
  3. Структурному анализу в комбинаторной оптимизации
  4. Приложениям алгебраической комбинаторики

Библиография

Статья цитирует ключевые работы в данной области, включая:

  • Оригинальные работы Брауна, Эрдёша и Шоша
  • Прорывные результаты Делькура-Постла
  • Серию работ Глока и соавторов
  • Результаты обобщения Шанггуаня
  • Работы Беннетта и др. об обобщённых числах Рамсея

Общая оценка: Это высококачественная работа по теоретической комбинаторике, достигшая значительного прогресса в исследовании проблемы Брауна-Эрдёша-Шоша. Хотя основная открытая проблема (случай r=3r=3) остаётся полностью нерешённой, технические вклады и методологические инновации статьи создают прочную основу для последующих исследований в данной области.