# A formula to compute the lovasz number

As Wikipedia says:

Let $G=(V,E)$ be a graph on $n$ vertices. An ordered set of $n$ unit vectors $U=(u_i |i \in V) \subset R^N$ is called an orthonormal representation of $G$ in $R^N$, if $u_i$ and $u_j$ are orthogonal whenever vertices $i$ and $j$ are $not$ adjacent in $G$: $$u_i^\mathrm{T} u_j = \begin{cases} 1, & \mbox{if }i = j, \\ 0, & \mbox{if }ij \notin E. \end{cases}$$ Clearly, every graph admits an orthonormal representation with $N = n$ (just represent vertices by distinct vectors from the standard basis of $R^n$), but in general it might be possible to take $N$ considerably smaller than the number of vertices $n$. The Lovász number $ϑ$ of graph $G$ is defined as follows: $$ϑ(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$.

At last, the question is Does it suffice to consider the minimal allowed $N$ in the above formula?

• What is $N$? What is $n$? – Chris Godsil Sep 27 '13 at 1:29
• @ChrisGodsil Thanks! I update the question. – Eden Harder Sep 27 '13 at 1:47

Yes, it does suffice to use the minimum possible value of $N$. (This is discussed in the wikipedia article, for example.) One problem is that it is not easy to determine this minimum value.