RUS  ENG
Полная версия
ЖУРНАЛЫ // Записки научных семинаров ПОМИ // Архив

Зап. научн. сем. ПОМИ, 2024, том 534, страницы 128–146 (Mi znsl7480)

О кликовом числе тотального графа $2\times n$ и $3\times 3$ матриц

А. М. Максаевab, В. В. Промысловab, Д. С. Шешеняa

a Национальный исследовательский университет “Высшая школа экономики”, Москва, 101000, Россия
b Московский Центр фундаментальной и прикладной математики, Москва, 119991, Россия

Аннотация: Тотальным графом пространства $ m \times n $ матриц над полем $\mathbb F$ называется граф с множеством вершин $ M_{m \times n}(\mathbb F),$ где различные матрицы $ A $ и $ B $ соединены ребром, если и только если $\operatorname{rank}(A + B) < \min(m,n)$. В работе доказывается, что над полем порядка $q$, где $q$ – степень нечетного простого числа, кликовое число тотального графа $2 \times n$ матриц равно $q^n$, а $3 \times 3$ матриц – $O(q^6)$. До настоящего момента данный вопрос был исследован только для $2 \times 2$ матриц. Библ. – 8 назв.

Ключевые слова: кликовое число графа, тотальный граф, комбинаторная теория матриц.

УДК: 519.174

Поступило: 01.10.2024



© МИАН, 2025