Совершенные раскраски гиперграфов и их спектры

Совершенной $k$-раскраской гиперграфа назовем такую раскраску его вершин в $k$ цветов, что цвет вершины однозначно задает раскраску инцидентных ей гиперребер. Одним из наиболее простых примеров совершенных раскрасок является трансверсаль в однородном регулярном гиперграфе. Другой важный пример — это накрытия одного гиперграфа другим, сохраняющие отношения инцидентности между вершинами и гиперребрами. В то время как теория совершенных раскрасок графов уже достаточно обширна, аналогичные вопросы для гиперграфов практически не изучены. В этом докладе мы покажем, что многие хорошие алгебраические свойства совершенных раскрасок графов остаются верными и для гиперграфов.
Прежде всего будет получено многомерное матричное уравнение на совершенные раскраски гиперграфов и их параметры. Затем докажем, что собственные числа многомерной матрицы параметров совершенной раскраски обязаны быть собственными числами матрицы смежности гиперграфа. Кроме того, будет доказан аналог теоремы о существовании общего накрытия для гиперграфов. Наконец, в качестве примеров мы вычислим параметры совершенных $2$-раскрасок $3$-однородных гиперграфов, установим параметры кратных трансверсалей как совершенных раскрасок и найдем все совершенные $2$-раскраски для $3$-однородного гиперграфа, заданного плоскостью Фано.
Исследование выполнено за счет гранта Российского научного фонда № 22-21-00202.