Opened 4 years ago

Last modified 3 years ago

#18869 new enhancement

add more versions of Lovasz theta for graphs

Reported by: dimpase Owned by:
Priority: major Milestone: sage-7.5
Component: graph theory Keywords:
Cc: krishnaniyer97@… Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by dimpase)

There are variations by Schrijver and Szegedy of Lovasz theta which are computable using SDP, just as the one from #18830.

An implementation calling the standard in Sage SDP solver from cvxopt is available as a gist by Dan Stahlke, who kindly gave us permission to include parts of it into Sage under GPL.


Szegedy, M., “ A note on the number of Lovasz and the generalized Delsarte bound”, In proceedings of 35th Annual Symposium on Foundations of Computer Science, 36–39 (1994)

for the corresponding definitions.

Change History (3)

comment:1 Changed 3 years ago by dimpase

  • Cc ncohen removed
  • Milestone changed from sage-6.8 to sage-7.5

comment:2 Changed 3 years ago by zombie

  • Cc krishnaniyer97@… added

comment:3 Changed 3 years ago by dimpase

  • Description modified (diff)
Note: See TracTickets for help on using tickets.