# How to compute the Lovász number for the given graph in Mathematica?

Here is a graph whose adjacency matrix is

m = {
{0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0},
{0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0},
{0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1},
{0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1},
{0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1},
{1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1},
{1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0},
{1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0},
{1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1},
{1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0},
{0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0},
{0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0}
};


then how to compute its Lovász number in Mathematica? I think this is a common question. Any help or suggestions will be appreciated!

Here are three ways to do the computation, which is the best one to compile in Mathematica and how?

1.Let $G=(V,E)$ be a graph on $n$ vertices. Let $A$ range over all $n*n$ symmetric matrix|symmetric matrices such that $a_{ij}=1$ whenever $i=j$ or $ij∉E$, and let $λ_{max}(A)$ denote the largest eigenvalue of $A$. Then an alternative way of computing the Lovász number of $G$ is as follows: $$\vartheta(G) = \min_A \lambda_\text{max}(A).$$

2.The following method is dual to the previous one. Let $B$ range over all $n*n$ symmetric positive semidefinite matrix such that $b_{ij'}=0$ for every $ij ∈ E$ and $Tr(B)=1$. Here $Tr$ denotes trace (the sum of diagonal entries) and $J$ is the $n*n$ matrix of ones. Then $$\vartheta(G) = \max_B \operatorname{Tr}(BJ).$$ Note that $Tr(BJ)$ is just the sum of all entries of $B$.

3.The Lovász number can be computed also in terms of the complement graph $\bar{G}$. Let $d$ be a unit vector and $V = (v_i | i ∈ V)$ be an orthonormal representation of $\bar{G}$. Then $$\vartheta(G) = \max_{d,V} \sum_{i \in V} (d^\mathrm{T} v_i)^2.$$

Though PlatoManiac provided a helpful link, that way can not go through on my computer.

• Here is a code mathematica-bits.blogspot.de/2011/03/… – PlatoManiac Sep 25 '13 at 14:07
• @PlatoManiac Thanks a lot! But it is too hard to install that package for me. Is there any other way? – Eden Harder Sep 26 '13 at 14:25
• @PlatoManiac I tried to install one needed file cvxopt but failed in my ubuntu 13.04. So, some other way may be better for me. Thanks! – Eden Harder Sep 26 '13 at 14:56
• @EdenHarder Consider that very likely it is considerably harder to write the function from scratch than to install the package. – Szabolcs Sep 27 '13 at 13:55
• @Szabolcs Yeap, but there are too many obstacles in the way to install that package. I try the random method but it seems not efficient. – Eden Harder Sep 28 '13 at 1:53