Двудольное число Турана путей и других деревьев

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

• ID статьи: 2511.07374
• Название: Bipartite Turán number of paths and other trees
• Авторы: Marthe Bonamy, Théotime Leclere, Timothé Picavet
• Учреждения: CNRS, LaBRI, Université de Bordeaux; ENS Paris-Saclay
• Классификация: math.CO (комбинаторика), cs.DM (дискретная математика)
• Дата публикации: 11 ноября 2025 г.
• Ссылка на статью: https://arxiv.org/abs/2511.07374

Аннотация

В данной работе полностью решена недавно поставленная Каро, Паткошем и Тузой задача: определение точного максимального числа рёбер в связной двудольной графе, которое является функцией длины наибольшего пути в графе и количества вершин по обе стороны двудольного разбиения. Ранее эта задача была известна только для двудольных графов с равными размерами долей и наибольшей длиной пути не более 5. Статья также обсуждает возможные обобщения путём замены «пути» на деревья определённых типов.

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

Предпосылки задачи

1. Классическая задача Турана: Теорема Турана определяет максимальное число рёбер в графе на n вершинах, не содержащем полный подграф заданного порядка, что положило начало систематическому изучению экстремальных задач на запрещённые подграфы.
2. Ограничения теоремы Эрдёша-Стоуна: Эта теорема асимптотически даёт число Турана для всех недвудольных запрещённых графов, но не предоставляет никакой информации для двудольного случая.
3. Особенность двудольных графов: Задача Турана для двудольных графов остаётся открытой и порождает несколько центральных гипотез, наиболее известная из которых — гипотеза Эрдёша-Соша: граф на n вершинах, исключающий дерево из k вершин, имеет не более (k-2)n/2 рёбер.
4. Исследование связных двудольных графов: Каро, Паткош и Туза CPT25 недавно сосредоточили внимание на случае, когда хозяйский граф одновременно двудолен и связен, введя обозначение exb,c(a,b,H) для максимального числа рёбер в связном двудольном графе с долями размеров a и b, не содержащем H в качестве подграфа.

Мотивация исследования

• Ограничения известных результатов: CPT25 решила задачу только для всех деревьев из 6 или менее вершин, двойных звёзд и некоторых графов-пауков, в частности, известно только exb,c(n,n,P₅) = exb,c(n,n,P₆) = 2n-1
• Открытые вопросы: Требуется определить exb,c(n,n,Pₖ) для произвольного пути Pₖ, по крайней мере дать асимптотическое значение
• Потребность в обобщении: Необходимо исследовать значения exb,c для определённых семейств деревьев

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

1. Полное решение задачи для путей: Для всех путей Pₖ даны точные значения exb,c(a,b,Pₖ), причём не только асимптотические значения, но и применимые к несбалансированным двудольным графам (основная теорема 1.5)
2. Расширение на графы-метлы: Для графов-метел Sp,d* (комбинация пути длины p и звезды с d ветвями) даны точные значения, когда звезда больше пути (теорема 1.6)
3. Результаты верхних границ: При условии, что звезда не превышает половину размера пути, предоставлены верхние границы (теорема 1.7)
4. Технические инновации: Разработаны новые методы работы со связными двудольными графами, включая лемму о существовании критических вершин и индуктивную схему

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

Определение задачи

Определение 1.1: Для фиксированных целых чисел a, b и графа H, exb,c(a,b,H) — это максимальное число рёбер в связном двудольном графе с долями размеров a и b, не содержащем H в качестве подграфа.

Данная работа в основном исследует:

• Входные данные: длина пути k, размеры долей двудольного графа a, b
• Выходные данные: точное значение exb,c(a,b,Pₖ)
• Ограничения: граф должен быть связным, двудольным и не содержать Pₖ в качестве подграфа

Основные теоремы

Теорема 1.5 (основной результат): Для всех k ≥ 3 и b ≥ a ≥ k, $\text{ex}_{b,c}(a,b,P_{2k}) = \text{ex}_{b,c}(a,b,P_{2k-1}) = (k-2)(b-1) + a$

Эта формула показывает:

• Пути нечётной и чётной длины имеют одинаковое число Турана
• Число рёбер растёт линейно с увеличением большей доли b с коэффициентом (k-2)
• Существует аддитивный корректирующий член a

Архитектура доказательства

1. Построение нижней границы (раздел 2)

Предложение 2.1 предоставляет конструктивное доказательство:

Построим граф G с двудольным разбиением A = {u₁,...,uₐ} и B = {v₁,...,vᵦ}:

• Первые k-2 вершин из A полностью соединены со всеми вершинами из B (образуя Kₖ₋₂,ᵦ)
• Оставшиеся a-(k-2) вершин из A являются листьями, все соединены с одной конкретной вершиной из B

Подсчёт рёбер: $|E(G)| = b(k-2) + (a-(k-2)) = (k-2)(b-1) + a$

Доказательство свойства P₂ₖ₋₁-свободности:

• Полный двудольный граф Kₖ₋₂,ᵦ имеет наибольший путь с 2k-3 вершинами
• Добавленные листья не могут удлинить путь, так как все они имеют степень 1

2. Доказательство верхней границы (раздел 3)

Используется метод математической индукции, ключевыми являются три леммы:

Лемма 3.2 (существование вершины малой степени): В большей доле B существует вершина x степени ≤ k-2, удаление которой сохраняет связность.

Идея доказательства:

• Используя поиск в глубину, найти лист b в B
• Если d(b) ≤ k-2, положить x = b
• Если d(b) = k-1, то длина пути должна быть 2k-2, образуя цикл
• В этом случае можно найти другую вершину b' степени ≤ k-2

Лемма 3.3 (пара удаляемых вершин в сбалансированном графе): Для сбалансированного двудольного графа существуют две вершины x, y такие, что d(x) + d(y) ≤ k-1 и их удаление сохраняет связность и сбалансированность.

Доказательство использует анализ концов наибольшего пути P:

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

Лемма 3.4 (базовый случай): Когда a = b = k, |E(G)| ≤ (k-1)² + 1.

Доказательство использует индукцию, ключевое наблюдение:

• Найти вершину x минимальной степени, не являющуюся точкой сочленения
• Удалить x и анализировать структуру оставшегося графа
• Использовать свойство P₂ₖ-свободности для ограничения степени и структуры

Доказательство основной теоремы:

• Если b > a: использовать лемму 3.2 для удаления вершины, затем индукция
• Если a = b > k: использовать лемму 3.3 для удаления двух вершин, затем индукция
• Если a = b = k: использовать лемму 3.4

Результаты для графов-метел

Теорема 1.6: Для k, d ≥ 2, когда n ≥ d²/2 и d > 2k, $\text{ex}_{b,c}(n,n,S_{2k,d}) = \text{ex}_{b,c}(n,n,S_{2k+1,d}) = nd$

Ключевые технические леммы:

Лемма 4.1: Если в графе существует вершина, не являющаяся концом пути длины 2k, то |E(G)| ≤ (k-1)(b+a)

Лемма 4.2: Если |E(G)| ≥ k(b+a)+1, то степень каждой вершины не превышает k+d-1

Доказательство комбинирует эти леммы, удаляя вершину максимальной степени и её соседей, используя связность и ограничения на степени для получения противоречия.

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

Как чистая теоретико-математическая работа, данная статья не содержит экспериментальной части; все результаты получены посредством строгих математических доказательств.

Экспериментальные результаты

Проверка основных результатов

Точные формулы для путей:

• Для P₅ и P₆: exb,c(n,n,P₅) = exb,c(n,n,P₆) = 2n-1
  • Используя формулу: при k=3, (3-2)(n-1)+n = n-1+n = 2n-1 ✓
• Для общего Pₖ: формула даёт точные значения для всех случаев, включая несбалансированные двудольные графы

Результаты для графов-метел:

• Когда звёздная часть доминирует (d > 2k), число Турана равно nd
• Это согласуется с ограничениями на максимальную степень

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

1. Обобщение предложения 1.2: Результаты данной работы полностью включают и обобщают exb,c(n,n,P₅) = 2n-1 из CPT25
2. Повышение общности:
   • Расширение от сбалансированных графов к несбалансированным
   • Расширение от конкретных малых путей к произвольным путям
   • От асимптотических результатов к точным формулам

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

Классические результаты

1. Теорема Турана Tur45: Экстремальная задача для полных графов
2. Теорема Эрдёша-Стоуна ES46: Асимптотическое число Турана для недвудольных графов
3. Галлаи-Эрдёш GE59: Асимптотические результаты для связных графов, исключающих пути фиксированного размера
4. Гиярфаш-Руссо-Шелп GRS84: Точные числа Турана для двудольных графов, исключающих пути фиксированного размера

Непосредственно связанные работы

Каро-Паткош-Туза CPT25:

• Введение обозначения exb,c
• Решение задачи для малых деревьев (≤ 6 вершин)
• Решение для двойных звёзд и некоторых графов-пауков
• Постановка задачи, решённой в данной работе

Независимые работы

Хе-Салиа-Чжу HSZ25: Авторы упоминают независимую работу с аналогичными результатами, поданную в тот же день

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

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

1. Полный ответ на вопрос 1.3: Даны точные значения exb,c(n,n,Pₖ) для всех путей Pₖ, превосходя требуемые асимптотические значения
2. Частичный ответ на вопрос 1.4: Для семейства графов-метел в определённом диапазоне параметров даны точные значения или верхние границы
3. Методологический вклад: Разработана новая техническая схема для работы с экстремальными задачами на связные двудольные графы

Ограничения

1. Ограничения для графов-метел:
   • Теорема 1.6 требует d > 2k и n ≥ d²/2
   • Теорема 1.7 даёт только верхнюю границу, не точное значение
   • Промежуточные случаи (d ≈ k) полностью не решены
2. Общий случай деревьев: Рассмотрены только пути и графы-метлы, более общие семейства деревьев остаются открытыми
3. Технические ограничения: Некоторые шаги доказательства зависят от специфических структурных свойств и могут быть сложны для обобщения на более сложные запрещённые подграфы

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

1. Совершенствование результатов для графов-метел: Определение точных значений для всех диапазонов параметров
2. Расширение на другие семейства деревьев:
   • Полная характеризация графов-пауков
   • Другие специальные древовидные структуры
3. Углублённое исследование несбалансированного случая: Хотя данная работа рассматривает случай a ≠ b, возможны более тонкие результаты
4. Вычислительная сложность: Исследование алгоритмических проблем определения, достигает ли данный граф границы Турана

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

Достоинства

1. Полное решение открытой задачи:
   • Не только ответ на вопрос 1.3, но и более сильная точная формула
   • Расширение на несбалансированные двудольные графы повышает общность результатов
2. Элегантная техника доказательства:
   • Построение нижней границы просто и ясно
   • Структура индуктивного доказательства верхней границы прозрачна
   • Ключевые леммы (3.2, 3.3, 3.4) сформулированы и доказаны лаконично
3. Полнота результатов:
   • Для путей даны точные формулы для всех параметров
   • Форма формулы проста: (k-2)(b-1)+a
   • Единообразная обработка путей нечётной и чётной длины
4. Качество изложения:
   • Структура статьи ясна, логика строга
   • Ключевые шаги поддержаны детальными вспомогательными предложениями
   • Иллюстрации (например, рисунок 1) помогают понять построения
5. Технические инновации:
   • Лемма 3.2 о существовании вершины малой степени, не являющейся точкой сочленения, — ключевое озарение
   • Характеризация удаляемых пар вершин в сбалансированном графе (лемма 3.3) имеет самостоятельную ценность
   • Использование поиска в глубину пронизывает доказательство, демонстрируя эффективное применение классических инструментов

Недостатки

1. Неполнота результатов для графов-метел:
   • Существует пробел в параметрах между теоремами 1.6 и 1.7
   • Теорема 1.7 даёт только верхнюю границу 2nk+1, разрыв с возможным точным значением неизвестен
   • Условие n ≥ d²/2 выглядит технически сложным, возможно, не оптимальным
2. Сложность доказательства базового случая:
   • Доказательство леммы 3.4 (случай a=b=k) занимает значительное место
   • Требует нескольких вспомогательных утверждений (Claims 3.11-3.13)
   • Возможно существование более прямого аргумента
3. Ограниченная обобщаемость:
   • Метод сильно зависит от специфических структур путей и графов-метел
   • Для общих деревьев неясно, как применить эти методы
   • Не обсуждается возможная единая схема
4. Отношение к независимой работе:
   • Упоминается независимая работа HSZ25, но подробное сравнение отсутствует
   • Неясно, используют ли обе работы одинаковые технические методы

Влияние

1. Теоретический вклад:
   • Полное решение явно поставленной открытой задачи
   • Предоставление новых технических инструментов для экстремальных задач на связные двудольные графы
   • Точность результатов делает их эталонными в данной области
2. Методологическая ценность:
   • Индуктивная схема может быть применима к другим задачам на запрещённые подграфы
   • Ключевые леммы могут быть полезны в других контекстах
3. Последующие исследования:
   • Естественным образом возникает задача полной характеризации графов-метел
   • Мотивирует исследование значений exb,c для других семейств деревьев
   • Может вдохновить исследование несвязного случая
4. Проверяемость:
   • Как чистый теоретический результат, может быть проверен путём анализа доказательства
   • Построения явные и легко понимаемы
   • Формула проста, удобна для применения и цитирования

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

1. Теоретические исследования:
   • Справочный результат для исследователей экстремальной теории графов
   • Источник методов для задач типа Турана
   • Тематическое исследование экстремальных задач при ограничении связности
2. Связанные задачи:
   • Возможное вдохновение для исследований гипотезы Эрдёша-Соша
   • Контрастные данные для чисел Турана других деревьев
   • Исследование структурных свойств связных двудольных графов
3. Педагогическая ценность:
   • Демонстрация применения метода математической индукции в экстремальной комбинаторике
   • Пример анализа путей и поиска в глубину
   • Полный случай совпадения верхней и нижней границ

Справочные материалы (ключевые источники)

1. CPT25 Caro, Patkós, Tuza: Bipartite Turán number of trees — постановка задачи, решённой в данной работе
2. Tur45 Turán: On an extremal problem in graph theory — основание теории задач Турана
3. ES46 Erdős, Stone: On the structure of linear graphs — теорема Эрдёша-Стоуна
4. GRS84 Gyárfás, Rousseau, Schelp: An extremal problem for paths in bipartite graphs — точные числа Турана для путей в двудольных графах (без требования связности)
5. HSZ25 He, Salia, Zhu: The connected bipartite Turán problem for long cycles and paths — независимая связанная работа

Общая оценка

Это высокачественная работа по комбинаторной математике, полностью решающая явно поставленную открытую задачу и дающая результаты, превосходящие требуемые. Техника доказательства элегантна и инновативна, результаты полны и точны. Хотя остаётся работа по обобщению на общий случай деревьев, статья даёт решающий ответ для случая путей. Эта работа вносит существенный вклад в исследование экстремальных задач на связные двудольные графы и, как ожидается, станет важным справочным материалом в данной области.