|
|
Вторая конференция Математических центров России. Секция «Комбинаторика, дискретная геометрия, случайные структуры»
7 ноября 2022 г. 16:20–16:50, г. Москва, Ломоносовский корпус МГУ, аудитория В4, Ломоносовский пр., 27, к. 1
|
|
|
|
|
|
Совершенные раскраски гиперграфов и их спектры
А. А. Тараненко |
Количество просмотров: |
Эта страница: | 47 | Материалы: | 2 |
|
Аннотация:
Совершенной $k$-раскраской гиперграфа назовем такую раскраску его вершин в $k$ цветов, что цвет вершины однозначно задает раскраску инцидентных ей гиперребер. Одним из наиболее простых примеров совершенных раскрасок является трансверсаль в однородном регулярном гиперграфе. Другой важный пример — это накрытия одного гиперграфа другим, сохраняющие отношения инцидентности между вершинами и гиперребрами. В то время как теория совершенных раскрасок графов уже достаточно обширна, аналогичные вопросы для гиперграфов практически не изучены. В этом докладе мы покажем, что многие хорошие алгебраические свойства совершенных раскрасок графов остаются верными и для гиперграфов.
Прежде всего будет получено многомерное матричное уравнение на совершенные раскраски гиперграфов и их параметры. Затем докажем, что собственные числа многомерной матрицы параметров совершенной раскраски обязаны быть собственными числами матрицы смежности гиперграфа. Кроме того, будет доказан аналог теоремы о существовании общего накрытия для гиперграфов. Наконец, в качестве примеров мы вычислим параметры совершенных $2$-раскрасок $3$-однородных гиперграфов, установим параметры кратных трансверсалей как совершенных раскрасок и найдем все совершенные $2$-раскраски для $3$-однородного гиперграфа, заданного плоскостью Фано.
Исследование выполнено за счет гранта Российского научного фонда № 22-21-00202.
Дополнительные материалы:
ТараненкоАА.pdf (487.8 Kb)
|
|