Число Ловаса

Пусть G = (V, E) — граф с n вершинами. Упорядоченное множество n единичных векторов ${\displaystyle U=(u_{i}\mid i\in V)\subset \mathbf {R} ^{N}}$ называется ортонормальным представлением графа G в R^N, если u_i и u_j ортогональны, когда вершины i и j несмежны в G:

${\displaystyle u_{i}^{\mathrm {T} }u_{j}={\begin{cases}1,&i=j,\\0,&ij\notin E.\end{cases}}}$

Ясно, что любой граф допускает ортонормальное представление с N=n (просто вершинам сопоставим вершины различных векторов стандартного базиса пространства Rⁿ, хотя такое представление не является правильным (произведение векторов равно нулю, даже если соответствующие вершины смежны), разве что граф вообще не имеет рёбер. Правильное представление для N = n возможно, однако, в общем случае, N может быть существенно меньше числа вершин n.

Число Ловаса ϑ графа G определяется следующим образом:

${\displaystyle \vartheta (G)=\min _{c,U}\max _{i\in V}{\frac {1}{(c^{\mathrm {T} }u_{i})^{2}}},}$

где c — единичный вектор в R^N, а U — ортонормальное представление G в R^N. Здесь минимизация неявно предполагается и по размерности N, однако без потери общности достаточно предположить N = n [2]. Интуитивно, это соответствует минимизации половины угла кругового конуса, содержащего векторы ортонормального представления графа G. Если оптимальный угол равен ${\displaystyle \phi }$, то ${\displaystyle \theta (G)=1/cos^{2}(\phi )}$ и c соответствует оси симметрии конуса[3].

Пусть G = (V, E) — граф с n вершинами. Пусть A — n × n симметричные матрицы, такие, что a_ij = 1 всякий раз, когда i = j или ${\displaystyle ij\notin E}$, и пусть ${\displaystyle \lambda _{max}(A)}$ обозначает наибольшее собственное значение матрицы A. Тогда альтернативным способом вычисления числа Ловаса графа G является следующее[4]:

${\displaystyle \vartheta (G)=\min _{A}\lambda _{\max(}A).}$

Следующий метод является двойственным к предыдущему. Пусть B —n × n симметричные положительно определённые матрицы, такие, что b_ij = 0 для любого ${\displaystyle ij\in E}$ и Tr(B) = 1. Здесь Tr обозначает след (сумма диагональных элементов), а J является n × n матрицей единиц. Тогда[5]

${\displaystyle \vartheta (G)=\max _{B}\operatorname {Tr} (BJ).}$

Tr(BJ) просто равна сумме всех элементов B.

Число Ловаса можно вычислить в терминах дополнения графа G. Пусть d — единичный вектор и ${\displaystyle V=(v_{i}\mid i\in V)}$ — ортонормальное представление графа G[6].

${\displaystyle \vartheta (G)=\max _{d,V}\sum _{i\in V}(d^{\mathrm {T} }v_{i})^{2}.}$

Если ${\displaystyle G\boxtimes H}$ обозначает сильное произведение графов графов G и H, тогда[7]

${\displaystyle \vartheta (G\boxtimes H)=\vartheta (G)\vartheta (H).}$

Если G является дополнением графа G, то[8]

${\displaystyle \vartheta (G)\vartheta ({\bar {G}})\geq n,}$

и неравенство превращается в равенство, если граф G вершинно-транзитивен.

«Теорема сэндвича» Ловаса утверждает, что число Ловаса лежит между двумя другими числами, вычисление которых является NP-полной задачей[9]. Точнее,

${\displaystyle \omega (G)\leq \vartheta ({\bar {G}})\leq \chi (G),}$

где ${\displaystyle \omega (G)}$ — кликовое число графа G (размер наибольшей клики) а ${\displaystyle \chi (G)}$ — хроматическое число графа G (наименьшее число цветов, необходимое для раскраски вершин G так, что никакие две смежные вершины не раскрашены в один цвет). Однако значение ${\displaystyle \theta (G)}$ может быть аппроксимировано методом эллипсоидов за время, ограниченное полиномиальной функцией от числа вершин графа G[10].

Ёмкость Шеннона графа G определяется следующим образом:

${\displaystyle \Theta (G)=\sup _{k}{\sqrt[{k}]{\alpha (G^{k})}}=\lim _{k\rightarrow \infty }{\sqrt[{k}]{\alpha (G^{k})}},}$

где ${\displaystyle \alpha (G)}$ является числом независимости графа G (размер наибольшего независимого множества графа G), а G^k — сильное произведение графа G самого на себя k раз. Ясно, что ${\displaystyle \Theta (G)\geq \alpha (G)}$. Однако число Ловаса даёт верхнюю границу ёмкости Шеннона графа[11], поскольку

${\displaystyle \alpha (G)\leq \Theta (G)\leq \vartheta (G).}$

Граф пятиугольника

Например, пусть C₅ , пятиугольник, — граф малоразличимости сообщений для канала. С момента появления статьи Шеннона[12] встала задача определения значения ${\displaystyle \Theta (C_{5})}$. Ловас первым[1] установил, что ${\displaystyle \Theta (C_{5})={\sqrt {5}}}$.

Ясно, что ${\displaystyle \Theta (C_{5})\geq \alpha (C_{5})=2}$. Однако, ${\displaystyle \alpha (C_{5}^{2})\geq 5}$, поскольку «11», «23», «35», «54», «42» являются пятью взаимно различимыми сообщениями (образующие независимое множество из пяти вершин в сильном квадрате графа C₅, т.е. ${\displaystyle C_{5}\boxtimes C_{5}}$), так что ${\displaystyle \Theta (C_{5})\geq {\sqrt {5}}}$.

Чтобы показать, что эта граница является точной, пусть ${\displaystyle U=(u_{1},u_{2},u_{3},u4,u_{5})}$ будет ортонормальным представлением пятиугольника:

${\displaystyle u_{k}={\begin{pmatrix}\cos {\theta }\\\sin {\theta }\cos {\varphi _{k}}\\\sin {\theta }\sin {\varphi _{k}}\end{pmatrix}},\quad \cos {\theta }={\frac {1}{\sqrt[{4}]{5}}},\quad \varphi _{k}={\frac {2\pi k}{5}}}$

И пусть ${\displaystyle c=(1,0,0)}$. Если использовать эти величины в определении числа Ловаса, мы получим ${\displaystyle \theta (C_{5})\leq {\sqrt {5}}}$. Следовательно, ${\displaystyle \Theta (C_{5})={\sqrt {5}}}$.

Однако существуют графы, для которых число Ловаса и ёмкость Шеннона отличаются, так что число Ловаса не может быть использовано, в общем случае, для вычисления точной ёмкости Шеннона для графа[13].

Число Ловаса было обобщено для «некоммутативных графов» в контексте квантовой связи[14]. Число Ловаса возникает также в квантовой контекстуальности при попытке объяснить мощность квантовых компьютеров[15].

• Weisstein, Eric W. Lovász Number (англ.) на сайте Wolfram MathWorld.
• Weisstein, Eric W. Sandwich Theorem (англ.) на сайте Wolfram MathWorld.
• Weisstein, Eric W. Shannon Capacity (англ.) на сайте Wolfram MathWorld.