1
$\begingroup$

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?

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.