A formula to compute the lovasz number
As Wikipedia says:
The Lovász number $\vartheta$ of graph $G$ is defined as follows:
$$\vartheta(G) = \min\limits_{c, U} \max\limits_{i \in V}
\frac{1}{(c^\mathrm{T} u_i)^2},$$ where $c$ is a unit vector in $R^N$ and
$U$ is an orthonormal representation of $G$ in $R^N$. Here minimization
implicitly is performed also over the dimension $N$, however without loss
of generality it suffices to consider $N = n$.
Does it suffice to consider the minimal allowed $N$ in the above formula?
No comments:
Post a Comment