It talks about a graph database. My question isn't really about this database, but the fact that this database has the Lovasz number makes me wonder if Sage can calculate the Lovasz number of a graph???
BUMP: Did any one get the code (in the answer below) to work? It calls an error when I run it. And, I have no idea what the code is doing so I can't really figure out the error :)
File "/tmp/tmp0_qsPp/___code___.py", line 21, in lovasz_theta
c = -cvxopt.base.matrix([_sage_const_0p0 ]*(n-_sage_const_1 ) + [_sage_const_2p0 ]*(d-n))
TypeError: invalid type in list
Here you go. I've tested this against all of the graphs in the graph database. This code is adapted from someone's thesis which I found online. I cannot find the author's email address to ask if it can be made GPL or similar.
# Adapted from Program 4.2, page 44, of the dissertation of Constantinos
# Skarakis, http://keithbriggs.info/documents/Skarakis_MSc.pdf
'''Computes the Lovasz theta function for a graph.'''
Gc = G.complement()
n = Gc.num_verts()
m = Gc.num_edges()
# This case needs to be handled specially.
if n == 1: return 1.0
d = m+n
c = -cvxopt.base.matrix([0.0]*(n-1) + [2.0]*(d-n))
Xrow = [i*(1+n) for i in xrange(n-1)] + \
[b+a*n for (a, b, _w) in Gc.edge_iterator()]
Xcol = range(n-1) + range(d-1)[n-1:]
X = cvxopt.base.spmatrix(1.0, Xrow, Xcol, (n*n, d-1))
for i in xrange(n-1): X[n*n-1, i] = -1.0
sol = cvxopt.solvers.sdp(c, Gs=[-X], hs=[-cvxopt.base.matrix([0.0]*(n*n-1) + [-1.0], (n,n))])
v = 1.0 + cvxopt.base.matrix(-c, (1, d-1)) * sol['x']
# Some options I like to set.
cvxopt.solvers.options['show_progress'] = False
cvxopt.solvers.options['abstol'] = float(1e-10)
cvxopt.solvers.options['reltol'] = float(1e-10)
I did not use Sage to calculate the lovasz numbers in the database (I calculated this data before I knew about Sage!). It was a long time ago, and I couldn't find the program I used to calculate the information when I looked just now. It was probably at least related to one of the popular free semidefinite programming toolboxes from several years ago. IIRC, one of the sdp toolkits came with a theta function example program or something.