Доклады Российской академии наук. Математика, информатика, процессы управления, 2020, T. 490, № 1, стр. 78-80

Пусть $n > r > s$. Рассмотрим следующее семейство графов:

т.е. вершины графа – это всевозможные r-элементные подмножества $[n]: = {\text{\{ }}1,\; \ldots ,\;n{\text{\} }}$, а ребрами мы соединяем пары множеств, пересекающихся ровно по $s$ элементам. Эти графы называются графами Джонсона и играют важную роль в задачах теории кодирования (см. [1]), теории Рамсея (см. [2, 3]), комбинаторной геометрии (см. [4–8]), теории гиперграфов (см. [9–13]).

Определим клико-хроматическое число ${{\chi }_{c}}(G)$ графа $G$ как наименьшее число k, для которого существует такая раскраска вершин $G$ в $k$ цветов, что в ней все максимальные по включению клики (кроме изолированных вершин) неодноцветны. Эта величина изучалась многими авторами для различных семейств графов, включая графы Джонсона (см. [14, 15]).

Напомним, что ${{R}_{a}}(b,q)$ – это минимальное такое число $N$ (называемое числом Рамсея), что для любой раскраски ребер полного a-однородного гиперграфа на $N$ вершинах в $q$ цветов найдется одноцветный полный подгиперграф на $b$ вершинах. В работе [15] были, в частности, доказаны следующие две теоремы.

Теорема 1. Если $n > r > s > 0$ и $n \geqslant {{R}_{r}}(r + (r$ – – s)², q), то

Теорема 2. Если $n > r > 1$ и $n < {{R}_{r}}(r + 1$, q ‒ r – 1), то

Кажется, что для $s = r - 1$ теоремы 1 и 2 достаточно близки друг другу. Однако разница между параметрами q и $q - r - 1$ в числах Рамсея критична, ведь числа Рамсея растут как башни экспонент. Даже величина ${{R}_{a}}(b,2)$ зажата между функциями вида ${{t}_{{a - 1}}}(c{{b}^{2}})$ и ${{t}_{a}}(c{\text{'}}b)$, где $c$, $c{\text{'}}$ – положительные константы, а ${{t}_{1}}(x) = x$ и ${{t}_{{i + 1}}}(x) = {{2}^{{{{t}_{i}}(x)}}}$. Для большего числа цветов зависимость от этого числа попадает на вершины башен в верхних и нижних оценках. Нам удалось значительно усилить теорему 2, а при r = 2 найти точное значение клико-хроматического числа соответствующего графа. 

Теорема 3. Если $n\, > \,r\, > \,2$ и $2r\, - \,1\, \leqslant \,n\, < \,{{R}_{r}}$(r + 1, q – 2), то

Теорема 4. Если $n > 2$, то

При $s$, не обязательно равных $r - 1$, мы также нашли значительное количество ситуаций, в которых улучшаются ранее известные оценки.

Теорема 5. Пусть k, $c\, \in \,{{\mathbb{N}}_{0}}$, $c\, < \,{{2}^{k}}$, $r = {{2}^{{k + 1}}}$ + c, $s = {{2}^{k}} + c$. Тогда при n > r и $n \geqslant {{R}_{r}}(r + 2(r - s) - 1,q)$ верно ${{\chi }_{c}}(G(n,r,s)) > q$.

Теорема 6. Пусть $k > 0,$ $n > 2k$, $r = 2k$. Тогда если

то

Теорема 7. Пусть $k > 0,$ $n > 4k + 2$, s = = $2k + 1$, $r = 4k + 2$. Тогда если $\left[ {\tfrac{n}{s}} \right] \geqslant {{R}_{2}}(3,q)$, то ${{\chi }_{c}}(G(n,r,s)) > q$.

Наконец, мы нашли новые верхние и нижние оценки для случая r = 3, s = 1. Назовем гиперграф, изоморфный идуцированному подграфу $G(7,3,1)$ с множеством вершин

гиперграфом типа треугольник. Пусть ${{R}^{\vartriangle }}(q)$ – минимальное число N, при котором в любой раскраске ребер полного 3-однородного гиперграфа на N вершинах в q цветов найдется одноцветный подграф типа треугольник. (Очевидно, что ${{R}^{\Delta }}(q)\, \leqslant \,{{R}_{3}}(7$, q), т.е. функция определена корректно.)

Утверждение 1. Верна оценка ${{R}^{\Delta }}(q) \geqslant $ ≥ 3 ⋅  2^q + 1.

Теорема 8. Пусть $n > 8$. Тогда

1) если $n \geqslant {{R}^{\Delta }}(q)$, то ${{\chi }_{c}}(G(n,3,1)) > q$;

2) если $n < {{R}^{\Delta }}(q - 2)$, то ${{\chi }_{c}}(G(n,3,1)) \leqslant q$.

Выше приведена таблица 1, иллюстрирующая соотношения между результатами всех теорем настоящей работы. По горизонтали указывается значение r, по вертикали – значение s. В соответствующей клетке сначала указывается номер теоремы, дающей наилучшую нижнюю оценку клико-хроматического числа, а затем – номер теоремы, дающей наилучшую верхнюю оценку. В случае, если какой-либо оценки пока нет, в соответствующей графе стоит знак вопроса.