# Lovasz number

http://sage.math.washington.edu/tmp/s...

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???

Thanks

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

edit retag close merge delete

1

Try it with "python" selected in the notebook, not "sage". The problem is that cvxopt only takes very basic Python types for its lists, I guess. So when "Sage" types like RealNumbers come into play, cvxopt breaks. Using the program below with Sage tries to turn floats like 0.0 into "real numbers" like in Sage.

Note: the link in the question is no longer working, the current location for the corresponding page is:

Sort by » oldest newest most voted

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.

 import cvxopt.base import cvxopt.solvers # Adapted from Program 4.2, page 44, of the dissertation of Constantinos # Skarakis, http://keithbriggs.info/documents/Skarakis_MSc.pdf def lovasz_theta(G): '''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+an 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, (nn, d-1)) for i in xrange(n-1): X[nn-1, i] = -1.0 sol = cvxopt.solvers.sdp(c, Gs=[-X], hs=[-cvxopt.base.matrix([0.0](nn-1) + [-1.0], (n,n))]) v = 1.0 + cvxopt.base.matrix(-c, (1, d-1)) * sol['x'] return v # Some options I like to set. # http://abel.ee.ucla.edu/cvxopt/userguide/coneprog.html#algorithm-parameters cvxopt.solvers.options['show_progress'] = False cvxopt.solvers.options['abstol'] = float(1e-10) cvxopt.solvers.options['reltol'] = float(1e-10) #print lovasz_theta(graphs.CycleGraph(5)) 

more

nice! if we get permission to release it in GPL, can you post a patch to trac? On the other hand, as I understand it, short pieces of code are not copyrightable. Many projects say that it's okay to copy small bits of code, like less than 10 lines. It looks like this function is about 10 lines long, so it's probably okay to include it in Sage.

1

Note that this is probably pure Python. A workaround I found when searching for the error @G-Sage got is to do RealNumber = float ; Integer = int after importing the modules, if you wanted to do this inside of Sage.

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.

more

Here's a more updated link for this, which should stay up-to-date.

My very uneducated guess is that you can USE Sage to do this, but that it's not built in. Hopefully Jason Grout will see this - he is the source of this database, at least in part.

more