"Записки научных семинаров ПОМИ"
Том 534, стр. 128-146
О кликовом числе тотального графа $2\times n$ и $3\times 3$ матриц
А. М. Максаев, В. В. Промыслов, Д. С. Шешеня
Национальный исследовательский
университет ``Высшая школа экономики'',
Москва, 101000, Россия;
Московский Центр фундаментальной
и прикладной математики,
Москва, 119991, Россия
artmak95@mail.ru
valentin.promyslov@gmail.com
Национальный исследовательский
университет ``Высшая школа экономики'',
Москва, 101000, Россия
danil.sheshenya@yandex.ru
- Аннотация:
Тотальным графом пространства $ 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 назв.
- Ключевые слова: кликовое число графа, тотальный граф, комбинаторная теория матриц
[clique number of a graph, total graph, combinatorial matrix theory]
Полный текст(.pdf)