3
$\begingroup$

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.

$\endgroup$
  • 6
    $\begingroup$ Here is a code mathematica-bits.blogspot.de/2011/03/… $\endgroup$ – PlatoManiac Sep 25 '13 at 14:07
  • $\begingroup$ @PlatoManiac Thanks a lot! But it is too hard to install that package for me. Is there any other way? $\endgroup$ – Eden Harder Sep 26 '13 at 14:25
  • $\begingroup$ @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! $\endgroup$ – Eden Harder Sep 26 '13 at 14:56
  • 1
    $\begingroup$ @EdenHarder Consider that very likely it is considerably harder to write the function from scratch than to install the package. $\endgroup$ – Szabolcs Sep 27 '13 at 13:55
  • $\begingroup$ @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. $\endgroup$ – Eden Harder Sep 28 '13 at 1:53

Your Answer

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

Browse other questions tagged or ask your own question.