Solving SDPs arising from symmetric graphs: theory, software, applications

Solving large-scale SDPs with symmetries, e.g. computing Lovasz theta-function and its relatives on a graph, often presents a challenge of preparing the input for the SDP solver with as little manual labour as possible. We report on the work in progress, that is partially software-centric, that allows to solve these kinds of problems in a fully automated way: we use Sage (http://www.sagemath.org) to integrate GAP (http://www.gap-system.org), a computer algebra system that allows, among many other group-theorytic and combinatorial computations, for easy constructions of compact descriptions of (large) graphs with large automorphism groups, with CVXOPT (http://abel.ee.ucla.edu/cvxopt/), a suite of convex optimization routines. On the theory side, we generalise recent results of Schrijver and others on SDP-based bounds for codes to the general setting of bounding the coclique size in vertex-transitive graphs, and use it in computer-aided investigation of synchronizing groups (http://cameroncounts.wordpress.com/2010/04/06/synchronization/).