 Author
 Year
 2007
 Title
 Reduction of symmetric semidefinite programs using the regular *representation
 Journal
 Mathematical programming
 Volume  Issue number
 109  23
 Pages (fromto)
 613624
 Document type
 Article
 Faculty
 Faculty of Science (FNWI)
 Institute
 Kortewegde Vries Institute for Mathematics (KdVI)
 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 loworder 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}{m1},$$
where Z(m,n) is the Zarankiewicz number $$\lfloor\frac{1}{4}(m1)^2\rfloor\lfloor\frac{1}{4}(n1)^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  URL
 go to publisher's site
 Link
 Link
 Language
 Undefined/Unknown
 Permalink
 http://hdl.handle.net/11245/1.276167
Disclaimer/Complaints regulations
If you believe that digital publication of certain material infringes any of your rights or (privacy) interests, please let the Library know, stating your reasons. In case of a legitimate complaint, the Library will make the material inaccessible and/or remove it from the website. Please Ask the Library, or send a letter to: Library of the University of Amsterdam, Secretariat, Singel 425, 1012 WP Amsterdam, The Netherlands. You will be contacted as soon as possible.