2025-11-10T03:03:05.603358

Rainbow triangles sharing one common vertex or edge

Chen, Ning
Let $G$ be an edge-colored graph on $n$ vertices. For a vertex $v$, the \emph{color degree} of $v$ in $G$, denoted by $d^c(v)$, is the number of colors appearing on the edges incident with $v$. Denote by $δ^c(G)=\min\{d^c(v):v\in V(G)\}$. By a theorem of H. Li, an $n$-vertex edge-colored graph $G$ contains a rainbow triangle if $δ^c(G)\geq \frac{n+1}{2}$. Inspired by this result, we consider two related questions concerning edge-colored books and friendship subgraphs of edge-colored graphs. Let $k\geq 2$ be a positive integer. We prove that if $δ^c(G)\geq \frac{n+k-1}{2}$ where $n\geq 3k-2$, then $G$ contains $k$ rainbow triangles sharing one common edge; and if $δ^c(G)\geq \frac{n+2k-3}{2}$ where $n\geq 2k+9$, then $G$ contains $k$ rainbow triangles sharing one common vertex. The special case $k=2$ of both results improves H. Li's theorem. The main novelty of our proof of the first result is a combination of the recent new technique for finding rainbow cycles due to Czygrinow, Molla, Nagle, and Oursler and some recent counting technique from \cite{LNSZ}. The proof of the second result is with the aid of the machine implicitly in the work of Turán numbers for matching numbers due to Erdős and Gallai.
academic

Радужные треугольники, имеющие общую вершину или ребро

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

  • ID статьи: 2302.00851
  • Название: Rainbow triangles sharing one common vertex or edge
  • Авторы: Xiaozheng Chen (Чжэнчжоуский университет), Bo Ning (Университет Нанкай)
  • Классификация: math.CO (комбинаторика)
  • Дата публикации: 2 февраля 2023 г. (препринт arXiv)
  • Ссылка на статью: https://arxiv.org/abs/2302.00851

Аннотация

В данной работе исследуется проблема существования радужных треугольников в рёберно раскрашенных графах. Для рёберно раскрашенного графа GG с nn вершинами цветовая степень вершины vv определяется как dc(v)d^c(v) — количество различных цветов на рёбрах, инцидентных vv. Минимальная цветовая степень обозначается как δc(G)=min⁡{dc(v):v∈V(G)}\delta^c(G)=\min\{d^c(v):v\in V(G)\}. Теорема Х. Ли показывает, что при δc(G)≥n+12\delta^c(G)\geq \frac{n+1}{2} граф GG содержит радужный треугольник. Вдохновлённые этим результатом, авторы исследуют структуры книг (books) и графов дружбы (friendship graphs) в рёберно раскрашенных графах. Основные результаты доказывают: при δc(G)≥n+k−12\delta^c(G)\geq \frac{n+k-1}{2} и n≥3k−2n\geq 3k-2 граф GG содержит kk радужных треугольников, имеющих общее ребро; при δc(G)≥n+2k−32\delta^c(G)\geq \frac{n+2k-3}{2} и n≥2k+9n\geq 2k+9 граф GG содержит kk радужных треугольников, имеющих общую вершину.

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

Предпосылки проблемы

  1. Классическая задача о треугольниках: Мантель (1907) доказал, что граф без треугольников на nn вершинах содержит не более ⌊n24⌋\lfloor\frac{n^2}{4}\rfloor рёбер
  2. Структурированные треугольники: Эрдёш и другие исследовали числа Турана для книг BkB_k (kk треугольников с общим ребром) и графов дружбы FkF_k (kk треугольников с общей вершиной)
  3. Радужные подграфы: Радужные подграфы и правильно раскрашенные подграфы тесно связаны со многими свойствами графов, включая классические результаты устойчивости, гипотезу Бермонда-Томассена, гипотезу Каччетта-Хэггквиста и другие

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

  1. Обобщение теоремы Х. Ли: Х. Ли (2013) доказал, что условие минимальной цветовой степени δc(G)≥n+12\delta^c(G)\geq \frac{n+1}{2} гарантирует существование радужного треугольника
  2. Структурированные радужные треугольники: Естественно рассмотреть случаи, когда несколько радужных треугольников имеют общую вершину или ребро
  3. Связь с классической теорией графов: Обобщение классических концепций книг и графов дружбы на рёберно раскрашенные графы

Ограничения существующих методов

Существующие исследования радужных треугольников в основном сосредоточены на существовании отдельного треугольника; исследований структурированного расположения нескольких радужных треугольников (таких как общая вершина или ребро) проводится мало.

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

  1. Основная теорема 3: Доказано, что при δc(G)≥n+k−12\delta^c(G)\geq \frac{n+k-1}{2} и n≥3k−2n\geq 3k-2 граф GG содержит kk радужных треугольников с общим ребром (рёберно раскрашенная книга BkB_k)
  2. Основная теорема 4: Доказано, что при δc(G)≥n+2k−32\delta^c(G)\geq \frac{n+2k-3}{2} и n≥2k+9n\geq 2k+9 граф GG содержит kk радужных треугольников с общей вершиной (рёберно раскрашенный граф дружбы FkF_k)
  3. Улучшение теоремы Х. Ли: При k=2k=2 оба основных результата улучшают исходную теорему Х. Ли
  4. Техническое новшество: Объединены методы радужных циклов Чигринова и другие современные техники подсчёта
  5. Анализ экстремальности: Предоставлен анализ точности результатов и экстремальные конструкции

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

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

Вход: рёберно раскрашенный граф G=(V,E)G=(V,E), где ∣V∣=n|V|=n, функция раскраски рёбер C:E→{1,2,…,k}C:E\to \{1,2,\ldots,k\}Выход: определить, содержит ли GG kk радужных треугольников с общим ребром (или общей вершиной) Ограничения: минимальная цветовая степень δc(G)\delta^c(G) удовлетворяет определённому пороговому значению

Основные концепции и методы

1. Определения, связанные с цветовой степенью

  • Цветовая степень: dc(v)=∣{C(uv):u∈N(v)}∣d^c(v) = |\{C(uv) : u \in N(v)\}|
  • α\alpha-окрестность: Nα(v)={u∈N(v):C(uv)=α}N_\alpha(v) = \{u \in N(v) : C(uv) = \alpha\}
  • Одноцветная степень: dmon(v)=max⁡{∣Nα(v)∣:α∈C(G)}d^{mon}(v) = \max\{|N_\alpha(v)| : \alpha \in C(G)\}

2. Техника ограничения цветов

Введена концепция "ограничения цветов" Чигринова и др.:

  • Для вершины vv и X⊆N(v)X \subseteq N(v), если α=C(xy)\alpha = C(xy) такой, что vxyvxy образует радужный P3P_3 и α∉C(y,N(y)∖X)\alpha \notin C(y, N(y)\setminus X), то говорят, что пара (v,X)(v,X) ограничивает цвет α\alpha для yy
  • Обозначим σv,X(y)\sigma_{v,X}(y) количество цветов, ограниченных парой (v,X)(v,X)

3. Подсчёт радужных треугольников

  • rt(v)rt(v): количество радужных треугольников, содержащих вершину vv
  • rt(v,x)rt(v,x): количество радужных треугольников, содержащих одновременно вершины vv и xx
  • rt(v,X)=∑x∈Xrt(v,x)rt(v,X) = \sum_{x \in X} rt(v,x)

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

Лемма 7 (лемма подсчёта)

Для минимального по рёбрам графа GG и вершины vv имеет место: rt(v,Ni(v))≥∑x∈Ni(v)(dc(x)+dc(v)−n)+di(v)∑1≤j≤s(dj(v)−1)−di(v)(di(v)−1)−∑y∈N!(v)dvyc(y,Ni(v))rt(v,N_i(v)) \geq \sum_{x\in N_i(v)}(d^c(x) + d^c(v) - n) + d_i(v)\sum_{1\leq j\leq s}(d_j(v)-1) - d_i(v)(d_i(v)-1) - \sum_{y\in N^!(v)}d^c_{vy}(y,N_i(v))

где N!(v)=⋃α∈C(G){Nα(v):∣Nα(v)∣=1}N^!(v) = \bigcup_{\alpha\in C(G)}\{N_\alpha(v) : |N_\alpha(v)| = 1\}.

Лемма 9 (анализ одноцветной степени)

Для вершины vv с максимальной одноцветной степенью имеет место B(v)≥0B(v) \geq 0, и при B(v)=0B(v) = 0 существуют специальные структурные свойства.

Стратегия доказательства

Схема доказательства теоремы 3

  1. Предположим, что не существует kk радужных треугольников с общим ребром
  2. Выберем вершину vv с максимальной одноцветной степенью
  3. Применим неравенство подсчёта из леммы 7
  4. Доказываем от противного существование структуры, удовлетворяющей условиям

Схема доказательства теоремы 4

  1. Применим теорию Турана Эрдёша-Галлаи о числе паросочетаний
  2. Построим вспомогательный граф G△(v)G^\triangle(v) (образованный рёбрами радужных треугольников, содержащих vv)
  3. Анализируем число покрытия и число паросочетания графа G△(v)G^\triangle(v)
  4. Через тонкий анализ степеней получаем противоречие

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

Экстремальные конструкции

Пример 1: Построим сбалансированный полный 3-дольный граф G[V1,V2,V3]G[V_1,V_2,V_3], где ∣V(G)∣=3k−3|V(G)|=3k-3, ∣V1∣=∣V2∣=∣V3∣=k−1|V_1|=|V_2|=|V_3|=k-1, с правильной раскраской. Этот граф удовлетворяет dc(v)=n+k−12d^c(v) = \frac{n+k-1}{2}, но не содержит BkB_k или FkF_k, что доказывает точность условия "n≥3k−2n \geq 3k-2" в теореме 3.

Сравнительный анализ

Статья сравнивает результаты со следующими классическими результатами:

  • Теорема Х. Ли: δc(G)≥n+12\delta^c(G) \geq \frac{n+1}{2} гарантирует радужный треугольник
  • Результаты Эрдёша и др.: классические числа Турана для книг и графов дружбы
  • Случай без раскраски: соответствующие условия минимальной степени

Результаты экспериментов

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

СтруктураУсловие в работеТребование на вершиныУсловие Х. ЛиУлучшение
B2B_2δc≥n+12\delta^c \geq \frac{n+1}{2}n≥4n \geq 4δc≥n+12\delta^c \geq \frac{n+1}{2}Конструктивное улучшение
F2F_2δc≥n+12\delta^c \geq \frac{n+1}{2}n≥13n \geq 13δc≥n+12\delta^c \geq \frac{n+1}{2}Конструктивное улучшение
BkB_kδc≥n+k−12\delta^c \geq \frac{n+k-1}{2}n≥3k−2n \geq 3k-2—Новый результат
FkF_kδc≥n+2k−32\delta^c \geq \frac{n+2k-3}{2}n≥2k+9n \geq 2k+9—Новый результат

Анализ точности

  • Точность теоремы 3: Пример 1 показывает, что при n≤3k−3n \leq 3k-3 требуется более сильное условие δc≥n+k2\delta^c \geq \frac{n+k}{2}
  • Асимптотическая точность: При k=o(n)k = o(n) результаты асимптотически точны

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

Исследования радужных треугольников

  1. Х. Ли (2013): впервые доказал, что условие цветовой степени δc≥n+12\delta^c \geq \frac{n+1}{2} гарантирует радужный треугольник
  2. Б. Ли и др. (2014): доказали, что более слабое условие ∑vdc(v)≥n(n+1)2\sum_{v} d^c(v) \geq \frac{n(n+1)}{2} также достаточно
  3. Х. Ли и др. (2022): дали версию подсчёта радужных треугольников

Классические результаты теории графов

  1. Мантель (1907): верхняя граница числа рёбер в графе без треугольников
  2. Эрдёш-Эдвардс-Хадживанов-Никифоров: числа Турана для книг
  3. Эрдёш и др. (1995): числа Турана для графов дружбы

Технические методы

  1. Чигринов и др. (2021): техника ограничения цветов для радужных циклов
  2. Эрдёш-Галлаи (1959): теория Турана для числа паросочетаний

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

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

  1. Успешно обобщены классические результаты Х. Ли о радужных треугольниках на случай нескольких треугольников с общей структурой
  2. Установлены достаточные условия для существования книг и графов дружбы в рёберно раскрашенных графах
  3. Предоставлен анализ точности результатов и экстремальные конструкции

Ограничения

  1. Требования на число вершин: Условие n≥2k+9n \geq 2k+9 в теореме 4 относительно сильное
  2. Техническая сложность: Доказательства включают несколько сложных техник подсчёта и структурного анализа
  3. Степень обобщения: Результаты в основном относятся к специфическим моделям совместного использования (одно ребро или одна вершина)

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

  1. Более общие модели совместного использования: Исследование более сложных расположений радужных треугольников
  2. Другие радужные структуры: Обобщение на радужные циклы, радужные пути и т. д.
  3. Алгоритмические проблемы: Разработка эффективных алгоритмов поиска этих структур
  4. Случайные графы: Соответствующие результаты для случайно рёберно раскрашенных графов

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

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

  1. Значительный теоретический вклад: Успешное обобщение важного классического результата, установление новой теоретической базы
  2. Техническое новшество: Искусное объединение нескольких современных методов (ограничение цветов, методы подсчёта, теория Турана)
  3. Полнота результатов: Не только даны результаты существования, но и проведён анализ точности и экстремальные случаи
  4. Ясность изложения: Логичная структура статьи, понятная схема доказательств

Недостатки

  1. Высокая сложность доказательств: Много технических деталей, что может затруднить доступность результатов
  2. Область применения: В основном теоретические результаты, практические приложения недостаточно ясны
  3. Константные множители: Некоторые константы в условиях (например, 2k+92k+9) могут быть неоптимальными

Влияние

  1. Теоретическая ценность: Открывает новые направления исследований в экстремальной комбинаторике и теории радужных подграфов
  2. Методологический вклад: Методы доказательства могут быть применены к другим аналогичным задачам
  3. Основа для дальнейших исследований: Создаёт базу для исследования связанных проблем

Применимые сценарии

Данное исследование в основном применимо к:

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

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

Статья цитирует 29 важных работ, включая:

  • H. Li (2013): Rainbow C3C_3's and C4C_4's in edge-colored graphs
  • Erdős, Füredi, Gould, Gunderson (1995): Extremal graphs for intersecting triangles
  • Czygrinow, Molla, Nagle, Oursler (2021): On odd rainbow cycles in edge-colored graphs
  • И многие другие классические работы в области комбинаторики и теории графов