| Title | Reduction of symmetric semidefinite programs using the regular *-representation |
|---|---|
| Published in | MATH PROGRAM, Vol. 109, No. 2-3, p.613-624. ISSN 00255610. |
| Author | Klerk, de E.; Pasechnik, D.V.; Schrijver, A. |
| Date | 2007 |
| Type | article |
| Abstract | Abstract We consider semidefinite programming problems on which a permutation group is acting. We describe a general technique to reduce the size of such problems, exploiting the symmetry. The technique is based on a low-order matrix $$*$$-representation of the commutant (centralizer ring) of the matrix algebra generated by the permutation matrices. We apply it to extending a method of de Klerk et al. that gives a semidefinite programming lower bound to the crossing number of complete bipartite graphs. It implies that cr(K 8,n ) ≥ 2.9299n 2 − 6n, cr(K 9,n ) ≥ 3.8676n 2 − 8n, and (for any m ≥ 9) $$\lim_{n\to\infty}\frac{{\rm cr}(K_{m,n})}{Z(m,n)}\geq 0.8594\frac{m}{m-1},$$ where Z(m,n) is the Zarankiewicz number $$\lfloor\frac{1}{4}(m-1)^2\rfloor\lfloor\frac{1}{4}(n-1)^2\rfloor$$, which is the conjectured value of cr(K m,n ). Here the best factor previously known was 0.8303 instead of 0.8594. Keywords Crossing numbers - Complete bipartite graph - Semidefinite programming - Regular $$*$$-representations |
| Publication | http://dare.uva.nl/record/286961 |
| OpenURL | Search this publication in (your) library |
| Persistent Identifier | urn:nbn:nl:ui:29-286961 |
| Metadata | XML |
| Repository | University of Amsterdam |
Go to page top
Go back to contents
Go back to site navigation