Переворотная раскраска графов II

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

• ID препринта: 2401.02315
• Название: Flip colouring of graphs II
• Автор: Xandru Mifsud (Университет Мальты)
• Классификация: math.CO (Комбинаторика)
• Дата публикации/конференция: Препринт arXiv, последняя версия (v3) от 4 ноября 2025 г.
• Ссылка на препринт: https://arxiv.org/abs/2401.02315

Аннотация

В данной работе исследуются две центральные проблемы переворотной раскраски графов. Для положительных целых чисел $b, r$ (где $b < r$) граф, являющийся $(b+r)$-регулярным, называется $(b,r)$-переворотным графом, если существует красно-синяя раскраска его рёбер такая, что каждая вершина имеет красную степень $r$ и синюю степень $b$, но для каждой вершины количество синих рёбер в её замкнутой окрестности превышает количество красных рёбер. В работе доказано: (1) для целых чисел $b, r$, удовлетворяющих $4 \leq b < r < b + 2\lfloor\frac{b+2}{6}\rfloor^2$, существуют малые $(b,r)$-переворотные графы с числом вершин $\Theta(b+r)$; (2) существуют $k$-переворотные последовательности $(a_1, \ldots, a_k)$ (при $k > 4$), в которых $a_k$ может быть произвольно большим, тогда как для $1 \leq i < \frac{k}{4}$ параметры $a_i$ остаются константами.

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

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

Переворотная раскраска представляет собой новый пример контраста локальных и глобальных явлений в теории графов. Для положительных целых чисел $b < r$ $(b,r)$-переворотный граф — это $(b+r)$-регулярный граф с раскраской рёбер, удовлетворяющей:

1. Глобальное большинство: синие рёбра образуют $b$-регулярный подграф, красные рёбра образуют $r$-регулярный подграф, поэтому глобально "красный цвет побеждает"
2. Локальный переворот: для каждой вершины $v$ количество синих рёбер в замкнутой окрестности $N[v]$ превышает количество красных рёбер, локально "синий цвет побеждает"

Это "переворотное" явление между локальным и глобальным уровнями отражает контринтуитивные свойства графов.

Значимость исследования

1. Теоретическое значение: переворотная раскраска входит в область исследования локально-глобальных явлений в теории графов, связана с классическими задачами о консенсусе большинства и локальных эффектах большинства
2. Комбинаторные структуры: исследование существования и методов построения регулярных графов со специальными свойствами
3. Параметрические отношения: изучение границ существования переворотных графов при различных параметрах и их минимальные размеры

Ограничения предыдущих исследований

Предыдущие работы 4 установили базовую теорию:

• Теорема 1.1: полностью характеризует существование 2-переворотных графов ($k=2$), доказывая существование $(b,r)$-переворотных графов при $3 \leq b < r \leq \binom{b+1}{2}-1$
• Теорема 1.2: даёт верхнюю границу минимального порядка $h(b,r)$, но эта граница достаточно слаба
• Теорема 1.3: доказывает, что для 3-переворотных графов $a_3 < 2(a_1)^2$, то есть максимальная степень цвета ограничена квадратичной функцией минимальной степени цвета
• Теорема 1.4: доказывает, что для $k > 3$ не существует подобного полиномиального соотношения ограничения

Мотивация данной работы

1. Улучшение верхних границ: поиск более точных границ $h(b,r)$, особенно в определённых диапазонах параметров
2. Количественное описание неограниченности: точная характеризация $q(k)$ — максимального индекса, при котором первые $q(k)$ параметров в $k$-переворотной последовательности могут оставаться константами, а последний параметр может быть произвольно большим

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

Основные вклады данной работы включают:

1. Улучшенная верхняя граница построения (Теорема 3.1): для $4 \leq b < r < b + 2\lfloor\frac{b+2}{6}\rfloor^2$ доказано $h(b,r) \leq 8\lambda_{b,r}\left(2 + \lfloor\frac{r}{2}\rfloor + \lfloor\frac{b+2}{2}\rfloor - 2\lfloor\frac{b+2}{6}\rfloor\right)$ где $\lambda_{b,r} = \max\{1, (b \bmod 2) + (r \bmod 2)\}$. Это значительно улучшает границу из предыдущих работ.
2. Точная граница для $q(k)$ (Теоремы 4.1 и 4.4): доказано, что для $k > 3$$\max\left\{1, \lceil\frac{k}{4}\rceil - 1\right\} \leq q(k) < \begin{cases} \frac{k}{3} & \text{если } k \equiv 0 \pmod{3}\\ \lceil\frac{k}{2}\rceil & \text{иначе} \end{cases}$
3. Разработка технических инструментов:
   • Систематизация операций произведения и упаковки рёбер в раскрашенных графах (Раздел 2)
   • Установление связи между построением графов Кэли и суммо-свободными множествами
   • Развитие методов построения на основе аддитивной комбинаторики
4. Результаты существования: доказано, что для $k \geq 4$ существуют $k$-переворотные последовательности, в которых первые $\lfloor k/4 \rfloor$ параметров могут оставаться константами, а последний параметр может быть произвольно большим

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

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

Задача $k$-переворотного графа: для $k \geq 2$, $d$-регулярного графа $G$ и возрастающей последовательности положительных целых чисел $a_1 < a_2 < \cdots < a_k$ (удовлетворяющей $d = \sum_{j=1}^k a_j$), существует ли $k$-цветная раскраска рёбер такая, что:

1. Рёбра цвета $j$ образуют $a_j$-регулярный подграф (то есть $\deg_j(v) = a_j$ для всех $v \in V$)
2. Для каждой вершины $v$ выполняется $e_k[v] < e_{k-1}[v] < \cdots < e_1[v]$ (количество рёбер каждого цвета в замкнутой окрестности убывает)

Обозначения:

• $N_G(v)$: открытая окрестность вершины $v$
• $N_G[v]$: замкнутая окрестность вершины $v$ ($N_G(v) \cup \{v\}$)
• $E_j^G(S)$: множество рёбер цвета $j$ в подграфе, индуцированном множеством вершин $S$
• $e_j^G[v]$: количество рёбер цвета $j$ в $N_G[v]$
• $\deg_j(v)$: количество рёбер цвета $j$, инцидентных вершине $v$

Основная техническая схема

1. Построение графов Кэли и суммо-свободных множеств (Раздел 3)

Определение графа Кэли: для группы $\Gamma$ и множества связей $S \subseteq \Gamma$ (замкнутого относительно инверсии и не содержащего единичного элемента), граф Кэли $\text{Cay}(\Gamma; S)$ имеет множество вершин $\Gamma$ и множество рёбер $\{\{g, gs\} : s \in S, g \in \Gamma\}$.

Суммо-свободное множество (Sum-free set): для абелевой группы $\Gamma$ и подмножества $A \subseteq \Gamma$, если $2A \cap A = \emptyset$ (где $2A = A + A$), то $A$ называется суммо-свободным множеством.

Ключевая лемма (Предложение 2.3): пусть $\Gamma$ — абелева группа, $R, B$ — непересекающиеся замкнутые относительно инверсии подмножества (не содержащие единичного элемента). Если $G = \text{Cay}(\Gamma; B)$ и $H = \text{Cay}(\Gamma; R)$ раскрашены в один цвет соответственно цветами 1 и 2, то в $\text{Cay}(\Gamma; B \cup R)$:

• $\deg_1(v) = \deg_G(v)$, $\deg_2(v) = \deg_H(v)$
• $e_1[v] - e_2[v] = (e_1^G[v] - e_2^H[v]) + (e_2^H(N_G(v)) - e_1^G(N_H(v)))$
• Ключевое свойство: если $(R + B) \cap R = \emptyset$ и $e_1^G[v] > e_2^H[v]$, то $e_1[v] > e_2[v]$

Стратегия построения (доказательство Теоремы 3.1):

1. Выбрать модуль $n = 8(2 + \lfloor r/2 \rfloor + \lfloor(b+2)/2\rfloor - 2\lfloor(b+2)/6\rfloor)$
2. В интервале $(n/8, n/4)$ выбрать два непересекающихся целых интервала $R_0$ и $T_0$
3. Построить множества:
   • $R_1 = R_0 \cup R_0^{-1}$ (размер $\lfloor r/2 \rfloor$)
   • $T_1 = T_0 \cup T_0^{-1}$, $B_1 = T_1 \cup 2T_2 \cup 2T_2^{-1}$ (где $T_2 \subseteq T_0$ размер $\lfloor(b+2)/6\rfloor$)
4. Проверка суммо-свободности (Лемма 3.2): путём тщательного выбора положения интервалов обеспечить $(R_1 + B_1) \cap R_1 = \emptyset$
5. Вычисление количества рёбер: используя то, что $2T_2$ — суммовое множество, $|2T_2| = 2|T_2| - 1$, точно достичь требуемой нижней границы количества рёбер $e_1^G[v] \geq b + 2\lfloor\frac{b+2}{6}\rfloor^2 > r = e_2^H[v]$
6. Обработка чётности: путём добавления инволюций (например, $n/2$ или использования прямого произведения $\mathbb{Z}_2 \times \mathbb{Z}_n$) скорректировать чётность $|R|$ и $|B|$

2. Произведения графов и упаковка (Раздел 2)

Сильное произведение (Strong Product): множество вершин $G \boxtimes H$ — это $V(G) \times V(H)$, ребро $\{(u,v), (u',v')\}$ существует тогда и только тогда, когда:

• $u = u'$ и $v \sim v'$ в $H$, или
• $v = v'$ и $u \sim u'$ в $G$, или
• $u \sim u'$ в $G$ и $v \sim v'$ в $H$

Лемма 2.1 (свойства сильного произведения): в $G \boxtimes H$$\deg_j((u,v)) = \deg_j^H(v) + \deg_j^G(u)(1 + \deg^H(v))$$e_j[(u,v)] = e_j^H[v](1 + \deg^G(u)) + e_j^G[u]\left(1 + \deg^H(v) + 2\sum_{i=1}^k e_i^H[v]\right)$

Декартово произведение: $G \square H$ содержит только "координатно-параллельные" рёбра (не включает диагональные рёбра).

Лемма 2.2 (свойства декартова произведения): $\deg_j((u,v)) = \deg_j^G(u) + \deg_j^H(v)$$e_j[(u,v)] = e_j^G[u] + e_j^H[v]$

3. Построение нижних границ (Раздел 4.2)

Основная идея: путём комбинирования нескольких малых переворотных графов построить большие переворотные графы, сохраняя первые $q$ параметров фиксированными и позволяя последнему параметру быть произвольно большим.

Лемма 4.3 (лемма комбинирования): если существует $(a_1, \ldots, a_q)$-переворотный граф $F$, удовлетворяющий $e_j^F[v] = D_j$ для всех $v$ и $1 \leq j \leq q$, и $D_q(k - 4q) > 1 + \xi q(q-1) + 5\binom{k-q}{2}$ где $\xi = \max_{1 \leq j < q}\{D_j - D_{j+1}\}$, то для любого $N$ существует $(a_1, \ldots, a_k)$-переворотный граф такой, что $a_k > N$.

Шаги построения:

1. Построить граф Кэли $K = \text{Cay}(\Gamma; S)$, где $S = \bigcup_{j=1}^{k-q-1} S_j$ — суммо-свободное множество
2. Вычислить декартово произведение $F \square K$
3. Построить двудольный граф $H$ и вычислить сильное произведение $H \boxtimes (F \square K)$
4. Путём выбора достаточно больших параметров $t$ обеспечить, чтобы степени цветов и количество рёбер в замкнутых окрестностях удовлетворяли условиям переворота

Теорема 4.4 (теорема существования): для $k > 3$ и $q = 1$ или $q < k/4$ существуют $a_1, \ldots, a_q \in \mathbb{N}$ такие, что для любого $N$ существует $(a_1, \ldots, a_k)$-переворотный граф, где $a_k > N$.

Доказательство использует Теорему 4.2 (существование переворотных интервалов) и комбинаторику Леммы 4.3.

4. Доказательство верхних границ (Раздел 4.1)

Теорема 4.1 (аргумент переокраски): путём переклассификации $k$ цветов в 2-цветные или 3-цветные, используя известные границы для 2-переворотных и 3-переворотных графов, доказано:

• Когда $k \equiv 0 \pmod{3}$: объединить каждые $k/3$ цветов, получить 3-переворотный граф, из Теоремы 1.3 получить $a_k \leq 2k^2(a_{k/3})^2$
• Иначе: объединить первые $\lceil k/2 \rceil$ цветов в один цвет, остальные цвета объединить в другой цвет, получить 2-переворотный граф, из Теоремы 1.1 получить квадратичную границу

Технические инновации

1. Глубокое объединение графов Кэли и суммо-свободных множеств: впервые систематически используется теория суммо-свободных множеств из аддитивной комбинаторики для построения переворотных графов, путём точного контроля положения интервалов достичь $(R+B) \cap R = \emptyset$
2. Многоуровневая схема произведений графов: инновационное объединение декартова произведения и сильного произведения, используя точные формулы Лемм 2.1 и 2.2 для контроля количества рёбер в замкнутых окрестностях
3. Оптимизация параметров: в Теореме 3.1 путём выбора размера $T_2$ равным $\lfloor(b+2)/6\rfloor$, используя свойство суммовых множеств $|2T_2| = 2|T_2| - 1$, точно достичь требуемой нижней границы количества рёбер
4. Обработка чётности: путём инволюций (involutions) и прямых произведений групп ловко обработать комбинации чётности $b$ и $r$
5. Техника переокраски: доказательство Теоремы 4.1 демонстрирует мощь объединения цветов при установлении верхних границ

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

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

Способы теоретической верификации

1. Конструктивные доказательства: Теоремы 3.1 и 4.4 доказывают существование путём явного построения
2. Комбинаторные аргументы: использование комбинаторного подсчёта и свойств групп для верификации условий на количество рёбер
3. Сравнительный анализ: Figure 6 показывает сравнение новых границ со старыми границами (для $b=11$ и $b=25$)

Численные примеры

Статья приводит конкретные примеры:

• Figure 1: минимально известный $(3,4)$-переворотный граф, 7 вершин
• Figure 5: схема построения графа Кэли при $(b,r) = (6,7)$ с $n=56$

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

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

1. Улучшенная верхняя граница (Теорема 3.1)

Для $4 \leq b < r < b + 2\lfloor(b+2)/6\rfloor^2$ новая граница: $h(b,r) \leq 8\lambda_{b,r}\left(2 + \lfloor\frac{r}{2}\rfloor + \lfloor\frac{b+2}{2}\rfloor - 2\lfloor\frac{b+2}{6}\rfloor\right) = O(b+r)$

В сравнении со старой границей из Теоремы 1.2: $h(b,r) \leq 2\left(r + b + 1 - \lfloor\frac{5+\sqrt{1+8(r-b)}}{2}\rfloor\right)\lfloor\frac{5+\sqrt{1+\sqrt{1+8(r-b)}}}{2}\rfloor$

Сравнение на Figure 6 (для $b=11$ и $b=25$):

• Для $b=11$, $r \in [13, 18]$: новая граница примерно 50-250, старая граница примерно 100-300
• Для $b=25$, $r \in [30, 55]$: новая граница примерно 200-800, старая граница примерно 400-1400
• Величина улучшения: снижение примерно на 30%-50%

Значимость: впервые доказано, что в данном диапазоне параметров $h(b,r) = \Theta(b+r)$, то есть оптимальный асимптотический порядок.

2. Граница для $q(k)$ (Уравнение 1)

$\max\left\{1, \lceil\frac{k}{4}\rceil - 1\right\} \leq q(k) < \begin{cases} \frac{k}{3} & \text{если } k \equiv 0 \pmod{3}\\ \lceil\frac{k}{2}\rceil & \text{иначе} \end{cases}$

Конкретные примеры:

• $k=4$: $0 \leq q(4) < 2$, следовательно $q(4) \in \{0, 1\}$
• $k=5$: $1 \leq q(5) < 3$, следовательно $q(5) \in \{1, 2\}$
• $k=6$: $1 \leq q(6) < 2$, следовательно $q(6) = 1$
• $k=12$: $2 \leq q(12) < 4$, следовательно $q(12) \in \{2, 3\}$

Значимость:

• Нижняя граница показывает, что по крайней мере первые $\lceil k/4 \rceil - 1$ параметров могут оставаться константами
• Верхняя граница показывает, что не более $k/3$ (или $\lceil k/2 \rceil$) параметров могут оставаться константами
• Это раскрывает фундаментальные ограничения на отношения между параметрами переворотных графов

Теоретические открытия

1. Явление фазового перехода:
   • При $k=2,3$: $h(a_1, \ldots, a_k)$ ограничена квадратичной функцией $a_1$
   • При $k \geq 4$: $h(a_1, \ldots, a_k)$ не может быть ограничена полиномиальной функцией $a_1, \ldots, a_{\lfloor k/4 \rfloor}$
2. Компактность построения: построение в Теореме 3.1 достигает порядка $\Theta(b+r)$, возможно близко к оптимальному
3. Зависимость параметров: граница для $q(k)$ показывает, что с увеличением числа цветов доля фиксируемых параметров уменьшается (от $1/2$ к $1/3$ к $1/4$)

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

Истоки переворотной раскраски

• 4 Caro, Lauri, Mifsud, Yuster, Zarb (2024): введение концепции переворотной раскраски, установление базовой теории (Теоремы 1.1-1.4)
• 8 Sheffield & Xi (2025): исследование связанных задач

Локально-глобальные явления

• 1 Abdullah & Draief (2015): локальное голосование большинства на графах и глобальный консенсус большинства
• 5 Caro & Yuster (2018): влияние локального большинства на глобальное большинство в связных графах
• 6 Fishburn, Hwang, Lee (1986): вынуждает ли локальное большинство глобальное большинство

Аддитивная комбинаторика

• 2 Alon & Kleitman (1990): исследование суммо-свободных подмножеств
• 7 Green & Ruzsa (2005): суммо-свободные множества в абелевых группах
• 9 Tao & Vu (2016): обзор суммо-свободных множеств в группах

Преимущества данной работы по сравнению с предыдущими:

1. Значительное улучшение верхней границы $h(b,r)$ (в определённом диапазоне)
2. Впервые точно определены границы для $q(k)$ (предыдущие работы знали только $q(k) \geq 1$)
3. Развита систематическая методология построения графов Кэли

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

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

1. Малые построения: для $4 \leq b < r < b + 2\lfloor(b+2)/6\rfloor^2$ существуют $(b,r)$-переворотные графы с $O(b+r)$ вершинами
2. Неограниченность параметров: для $k > 4$ можно построить $k$-переворотные последовательности, в которых первые $\lfloor k/4 \rfloor$ параметров остаются константами, а последний параметр может быть произвольно большим
3. Плотность границ: $q(k)$ зажата между $\Omega(k/4)$ и $O(k/2)$ (или $O(k/3)$)

Ограничения

1. Ограничение диапазона параметров: Теорема 3.1 применима только при $r < b + 2\lfloor(b+2)/6\rfloor^2$, для больших $r$ (близких к $\binom{b+1}{2}-1$) граница из Теоремы 1.2 остаётся лучше
2. Зазор в $q(k)$: между нижней границей $\lceil k/4 \rceil - 1$ и верхней границей $\lceil k/2 \rceil$ остаётся значительный зазор, точное значение неизвестно
3. Неабелевы группы: текущие построения в основном опираются на абелевы группы, случай неабелевых групп недостаточно исследован
4. Вычислительная сложность: статья не обсуждает алгоритмическую сложность определения, является ли данный граф переворотным

Будущие направления

Статья явно выдвигает две открытые проблемы:

Проблема 1: для $k \geq 4$, существует ли минимальное целое число $p(k)$ (где $k/4 \leq p(k) \leq k$), такое что $h(a_1, \ldots, a_k)$ ограничена полиномиальной функцией $a_{p(k)}$?

Проблема 2: для $3 \leq b < r \leq \binom{b+1}{2}-1$, каково максимальное значение $r$, при котором $h(b,r) = \Theta(b+r)$?

Другие потенциальные направления:

• Использование неабелевых групп для улучшения границ
• Точное определение значения $q(k)$
• Исследование структурных свойств переворотных графов (таких как диаметр, связность)
• Алгоритмические задачи: эффективное определение и построение переворотных графов

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

Достоинства

1. Теоретическая глубина:
   • Ловкое объединение графов Кэли, суммо-свободных множеств, произведений графов и других инструментов из разных областей
   • Строгие доказательства, конструктивные доказательства поддаются проверке
   • Тонкий анализ суммо-свободных множеств в Лемме 3.2 демонстрирует глубокие комбинаторные навыки
2. Значимость результатов:
   • Теорема 3.1 улучшает $h(b,r)$ с $O((r-b)^2)$ до $O(b+r)$, значительное улучшение
   • Впервые даны двусторонние границы для $q(k)$, заполнен теоретический пробел
   • Численное сравнение на Figure 6 наглядно демонстрирует эффект улучшения
3. Методологическая инновативность:
   • Предложение 2.3 устанавливает универсальную схему упаковки графов Кэли
   • Систематическая обработка произведений графов (Леммы 2.1-2.2) применима к другим задачам
   • Техника переокраски (Теорема 4.1) предоставляет новый подход к доказательству верхних границ
4. Ясность изложения:
   • Чёткая структура, от введения инструментов к применению, логичные уровни
   • Иллюстрации (Figures 1-5) помогают понять абстрактные построения
   • Полная система обозначений, удобна для отслеживания сложных доказательств

Недостатки

1. Ограниченная область применимости:
   • Ограничение параметров в Теореме 3.1 $r < b + 2\lfloor(b+2)/6\rfloor^2$ довольно строго, не охватывает случаи, когда $r$ близко к верхней границе $\binom{b+1}{2}-1$
   • При $b < 4$ новые результаты неприменимы
2. Проблема зазора:
   • Между нижней и верхней границами $q(k)$ остаётся зазор $O(k/4)$, точное значение неизвестно
   • Отсутствуют гипотезы или численные примеры точного значения $q(k)$
3. Сложность построения:
   • Построение графов Кэли требует тщательного выбора группы и множества связей, практическое применение может быть затруднено
   • Не обсуждается алгоритмическая эффективность построения
4. Недостаточное исследование неабелевых групп:
   • Работа в основном опирается на коммутативность абелевых групп, потенциал неабелевых групп недостаточно раскрыт
   • Ключевое доказательство Леммы 3.2 существенно использует коммутативность, обобщение на неабелевы группы требует новых идей
5. Недостаток конкретных примеров:
   • Кроме $(3,4)$ и $(6,7)$, отсутствуют другие конкретные примеры переворотных графов с малыми параметрами
   • Отсутствуют конкретные примеры $k$-переворотных последовательностей при $k \geq 4$

Влияние

1. Вклад в область:
   • Устанавливает прочную основу для теории переворотной раскраски, решает центральные проблемы предыдущих работ
   • Введённый метод графов Кэли может вдохновить исследования других локально-глобальных задач
   • Граница для $q(k)$ раскрывает фундаментальную сложность многоцветного переворота
2. Практическая ценность:
   • Переворотные графы могут иметь применение в проектировании сетей, алгоритмах консенсуса (хотя статья не исследует это)
   • Методы построения предоставляют новый способ генерирования регулярных графов со специальными свойствами
3. Воспроизводимость:
   • Все доказательства конструктивны, в принципе полностью воспроизводимы
   • Отсутствие кода или конкретных алгоритмов может потребовать дополнительной работы для практического построения
4. Последующие исследования:
   • Проблемы 1 и 2 указывают направления для будущих исследований
   • Определение точного значения $q(k)$ может потребовать новых техник
   • Расширение на нерегулярные графы, ориентированные графы и другие варианты заслуживает внимания

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

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

Ключевые ссылки

4 Y. Caro, J. Lauri, X Mifsud, R. Yuster, and C. Zarb. Flip colouring of graphs. Graphs and Combinatorics, 40(106), 2024.

• Введение переворотной раскраски, установление базовой теории

2 N. Alon and D. J. Kleitman. Sum-free subsets. In A Tribute to Paul Erdős, page 13–26. Cambridge University Press, 1990.

• Классические результаты о суммо-свободных множествах

7 B. Green and I. Z. Ruzsa. Sum-free sets in abelian groups. Israel Journal of Mathematics, 147(1):157–188, 2005.

• Глубокое исследование суммо-свободных множеств в абелевых группах

Общая оценка: это высококачественная теоретическая статья по комбинаторной математике, которая значительно продвигает теорию переворотной раскраски путём ловкого построения и тонкого анализа. Объединение графов Кэли и суммо-свободных множеств демонстрирует мощь кросс-дисциплинарных методов, улучшенные границы для $h(b,r)$ и $q(k)$ имеют важное теоретическое значение. Несмотря на ограничения диапазона параметров и наличие зазоров, статья создаёт прочную основу для последующих исследований, выдвинутые открытые проблемы имеют вызывающий характер и исследовательскую ценность. Рекомендуется исследователям, интересующимся экстремальной теорией графов, алгебраической теорией графов и аддитивной комбинаторикой.