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)
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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Borchers B. (1999) CSDP, a C library for semidefinite programming. Optim. Methods Softw. 11, 613–623
Brouwer A.E., Cohen A.M., Neumaier A. (1989) Distance-regular graphs. Springer, Berlin Heidelberg New York
Burrow M. (1965) Representation Theory of Finite Groups. Academic, New York
Gatermann K., Parrilo P.A. (2004) Symmetry groups, semidefinite programs, and sums of squares. J. Pure Appl. Algebra 192, 95–128
Kanno Y., Ohsaki M., Murota K., Katoh N. (2001) Group symmetry in interior-point methods for semidefinite programming. Optim. Eng. 2, 293–320
Kleitman D.J. (1970) The crossing number of K 5,n . J. Comb. Theory 9: 315–323
de Klerk E., Maharry J., Pasechnik D.V., Richter R.B., Salazar G. (2006) Improved bounds for the crossing numbers of K m,n and K n . SIAM J. Discret Math. 20, 189–202
Laurent, M.: Strengthened semidefinite programming bounds for codes. Math. Program. Ser. B, (this issue)
Schrijver A. (2005) New code upper bounds from the Terwilliger algebra and semidefinite programming. IEEE Trans. Inf. Theory 51, 2859–2866
Takesaki M. (1979) Theory of Operator Algebras I. Springer, Berlin Heidelberg New York
Woodall D.R. (1993) Cyclic-order graphs and Zarankiewicz’s crossing-number conjecture. J. Graph Theory 17, 657–671
Zarankiewicz K. (1954) On a problem of P. Turán concerning graphs. Fundam. Math. 41, 137–145
Author information
Authors and Affiliations
Corresponding author
Additional information
E. de Klerk was supported by the Netherlands Organization for Scientific Research grant NWO 613.000.214 as well as the NSERC grant 283331 - 04. Part of this research was performed while on leave from the Department of Combinatorics and Optimization, University of Waterloo. Part of this research was performed while D.V. Pasechnik held a position at CS Department, University of Frankfurt, supported by DFG grant SCHN-503/2-1.
Rights and permissions
About this article
Cite this article
de Klerk, E., Pasechnik, D.V. & Schrijver, A. Reduction of symmetric semidefinite programs using the regular \(\ast\)-representation. Math. Program. 109, 613–624 (2007). https://doi.org/10.1007/s10107-006-0039-7
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-006-0039-7