| 1 |
| Authors | E. de Klerk, D.V. Pasechnik, A. Schrijver | | Title | Reduction of symmetric semidefinite programs using the regular *-representation |
| Journal | MATH PROGRAM |
| Volume | 109 |
| Year | 2007 |
| Issue | 2-3 |
| Pages | 613-624 |
| ISSN | 00255610 |
| Faculty | Faculty of Science |
| Institute/dept. | FNWI: Korteweg-de 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 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 |
| Document type | Article |
| Document finder | 
|
Use this url to link to this page: http://dare.uva.nl/en/record/286961
Contact us about this recordNotify a colleague
Add to bookbag
|
