# Lovasz number

 1 I found this link: http://sage.math.washington.edu/tmp/sage-2.8.12.alpha0/doc/ref/module-sage.graphs.graph-database.html 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  asked Sep 10 '11 G-Sage 281 ● 1 ● 9 ● 24 It's conceivable that that is pure Python code?kcrisman (Aug 27 '12)@kcrisman Sorry, I don't know much. What would that tell us? :)G-Sage (Aug 27 '12)1Try 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.kcrisman (Aug 28 '12)

 1 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+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'] return v[0] # 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))  posted Dec 05 '11 dstahlke 36 ● 2 ● 3 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.Jason Grout (Dec 06 '11)But YANAL. :)kcrisman (Dec 06 '11)1Note 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. kcrisman (Aug 28 '12)@kcrisman Wow, thanks a lot!G-Sage (Aug 28 '12)
 2 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. posted Sep 10 '11 Jason Grout 3225 ● 7 ● 27 ● 72
 0 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. posted Sep 10 '11 kcrisman 6784 ● 14 ● 67 ● 152

[hide preview]