{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,24]],"date-time":"2025-08-24T01:57:57Z","timestamp":1756000677124,"version":"3.37.3"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2023,11,20]],"date-time":"2023-11-20T00:00:00Z","timestamp":1700438400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,11,20]],"date-time":"2023-11-20T00:00:00Z","timestamp":1700438400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2024,9]]},"abstract":"Abstract<\/jats:title>In this paper, we use semidefinite programming and representation theory to compute new lower bounds on the crossing number of the complete bipartite graph\u00a0$$K_{m,n}$$<\/jats:tex-math>\n \n K<\/mml:mi>\n \n m<\/mml:mi>\n ,<\/mml:mo>\n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, extending a method from de Klerk et al. (SIAM J Discrete Math 20:189\u2013202, 2006) and the subsequent reduction by De Klerk, Pasechnik and Schrijver (Math Prog Ser A and B 109:613\u2013624, 2007). We exploit the full symmetry of the problem using a novel decomposition technique. This results in a full block-diagonalization of the underlying matrix algebra, which we use to improve bounds on several concrete instances. Our results imply that $$\\mathop {\\textrm{cr}}\\limits (K_{10,n}) \\ge 4.87057 n^2 - 10n$$<\/jats:tex-math>\n \n cr<\/mml:mtext>\n \n (<\/mml:mo>\n \n K<\/mml:mi>\n \n 10<\/mml:mn>\n ,<\/mml:mo>\n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msub>\n )<\/mml:mo>\n <\/mml:mrow>\n \u2265<\/mml:mo>\n 4.87057<\/mml:mn>\n \n n<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n -<\/mml:mo>\n 10<\/mml:mn>\n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, $$\\mathop {\\textrm{cr}}\\limits (K_{11,n}) \\ge 5.99939 n^2-12.5n$$<\/jats:tex-math>\n \n cr<\/mml:mtext>\n \n (<\/mml:mo>\n \n K<\/mml:mi>\n \n 11<\/mml:mn>\n ,<\/mml:mo>\n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msub>\n )<\/mml:mo>\n <\/mml:mrow>\n \u2265<\/mml:mo>\n 5.99939<\/mml:mn>\n \n n<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n -<\/mml:mo>\n 12.5<\/mml:mn>\n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, $$ \\mathop {\\textrm{cr}}\\limits (K_{12,n}) \\ge 7.25579 n^2 - 15n$$<\/jats:tex-math>\n \n cr<\/mml:mtext>\n \n (<\/mml:mo>\n \n K<\/mml:mi>\n \n 12<\/mml:mn>\n ,<\/mml:mo>\n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msub>\n )<\/mml:mo>\n <\/mml:mrow>\n \u2265<\/mml:mo>\n 7.25579<\/mml:mn>\n \n n<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n -<\/mml:mo>\n 15<\/mml:mn>\n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, $$\\mathop {\\textrm{cr}}\\limits (K_{13,n}) \\ge 8.65675 n^2-18n$$<\/jats:tex-math>\n \n cr<\/mml:mtext>\n \n (<\/mml:mo>\n \n K<\/mml:mi>\n \n 13<\/mml:mn>\n ,<\/mml:mo>\n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msub>\n )<\/mml:mo>\n <\/mml:mrow>\n \u2265<\/mml:mo>\n 8.65675<\/mml:mn>\n \n n<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n -<\/mml:mo>\n 18<\/mml:mn>\n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> for all\u00a0n<\/jats:italic>. The latter three bounds are computed using a new and well-performing relaxation of the original semidefinite programming bound. This new relaxation is obtained by only requiring one small matrix block to be positive semidefinite.<\/jats:p>","DOI":"10.1007\/s10107-023-02028-1","type":"journal-article","created":{"date-parts":[[2023,11,20]],"date-time":"2023-11-20T07:02:31Z","timestamp":1700463751000},"page":"693-715","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["New lower bounds on crossing numbers of $$K_{m,n}$$ from semidefinite programming"],"prefix":"10.1007","volume":"207","author":[{"given":"Daniel","family":"Brosch","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4287-6479","authenticated-orcid":false,"given":"Sven","family":"C.\u00a0Polak","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,11,20]]},"reference":[{"key":"2028_CR1","doi-asserted-by":"publisher","first-page":"1261","DOI":"10.1137\/17M1158859","volume":"33","author":"J Balogh","year":"2019","unstructured":"Balogh, J., Lidick\u00fd, B., Salazar, G.: Closing in on Hill\u2019s conjecture. SIAM J. Discrete Math. 33, 1261\u20131276 (2019)","journal-title":"SIAM J. Discrete Math."},{"key":"2028_CR2","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1016\/j.procs.2023.08.216","volume":"223","author":"J Balogh","year":"2023","unstructured":"Balogh, J., Lidick\u00fd, B., Norin, S., Pfender, F., Salazar, G., Spiro, S.: Crossing numbers of complete bipartite graphs. Procedia Computer Science 223, 78\u201387 (2023)","journal-title":"Procedia Computer Science"},{"key":"2028_CR3","unstructured":"Brosch, D.: Symmetry reduction in convex optimization with applications in combinatorics. Ph.D. thesis, Tilburg University (2022)"},{"key":"2028_CR4","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511623677","volume-title":"Permutation Groups","author":"PJ Cameron","year":"1999","unstructured":"Cameron, P.J.: Permutation Groups. Cambridge University Press, Cambridge (1999)"},{"key":"2028_CR5","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1137\/S0895480104442741","volume":"20","author":"E de Klerk","year":"2006","unstructured":"de Klerk, E., Maharry, J., Pasechnik, D.V., Richter, R.B., Salazar, G.: Improved bounds for the crossing numbers of $$K_{m, n}$$ and $$K_n$$. SIAM J. Discrete Math. 20, 189\u2013202 (2006)","journal-title":"SIAM J. Discrete Math."},{"key":"2028_CR6","doi-asserted-by":"publisher","first-page":"613","DOI":"10.1007\/s10107-006-0039-7","volume":"109","author":"E de Klerk","year":"2007","unstructured":"de Klerk, E., Pasechnik, D., Schrijver, A.: Reductions of symmetric semidefinite programs using the regular $$\\ast $$-representation. Math. Program. 109, 613\u2013624 (2007)","journal-title":"Math. Program."},{"key":"2028_CR7","doi-asserted-by":"publisher","first-page":"659","DOI":"10.1007\/s10107-015-0879-0","volume":"151","author":"C Dobre","year":"2015","unstructured":"Dobre, C., Vera, J.: Exploiting symmetry in copositive programs via semidefinite hierarchies. Math. Program. Ser. B 151, 659\u2013680 (2015)","journal-title":"Math. Program. Ser. B"},{"key":"2028_CR8","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/j.jpaa.2003.12.011","volume":"192","author":"K Gatermann","year":"2004","unstructured":"Gatermann, K., Parrilo, P.A.: Symmetry groups, semidefinite programs, and sums of squares. J. Pure Appl. Algebra 192, 95\u2013128 (2004)","journal-title":"J. Pure Appl. Algebra"},{"key":"2028_CR9","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1080\/00029890.1973.11993230","volume":"80","author":"P Erd\u0151s","year":"1973","unstructured":"Erd\u0151s, P., Guy, R.K.: Crossing number problems. Am. Math. Mon. 80, 52\u201358 (1973)","journal-title":"Am. Math. Mon."},{"key":"2028_CR10","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1137\/0604033","volume":"4","author":"MR Garey","year":"1983","unstructured":"Garey, M.R., Johnson, D.S.: Crossing number is NP-complete. SIAM J. Algebraic Discrete Methods 4, 312\u2013316 (1983)","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"2028_CR11","unstructured":"Gijswijt, D.C.: Block diagonalization for algebras associated with block codes, arXiv:0910.4515 (2009)"},{"key":"2028_CR12","doi-asserted-by":"publisher","first-page":"2697","DOI":"10.1109\/TIT.2012.2184845","volume":"58","author":"DC Gijswijt","year":"2012","unstructured":"Gijswijt, D.C., Mittelmann, H.D., Schrijver, A.: Semidefinite code bounds based on quadruple distances. IEEE Trans. Inf. Theory 58, 2697\u20132705 (2012)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"2028_CR13","doi-asserted-by":"crossref","unstructured":"Hymabaccus, K., Pasechnik, D.: Decomposing Linear Representations of Finite Groups, arXiv:2007.02459 (2020)","DOI":"10.21105\/joss.01835"},{"key":"2028_CR14","volume-title":"Character Theory of Finite Groups","author":"M Isaacs","year":"1976","unstructured":"Isaacs, M.: Character Theory of Finite Groups. Academic Press, New York (1976)"},{"key":"2028_CR15","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/S0021-9800(70)80087-4","volume":"9","author":"DJ Kleitman","year":"1970","unstructured":"Kleitman, D.J.: The crossing number of $$K_{5, n}$$. J. Comb. Theory 9, 315\u2013323 (1970)","journal-title":"J. Comb. Theory"},{"key":"2028_CR16","first-page":"265","volume":"63","author":"W Kr\u00e1skiewicz","year":"2001","unstructured":"Kr\u00e1skiewicz, W., Weyman, J.: Algebra of coinvariants and the action of a Coxeter element. Bayreuth. Math. Schr. 63, 265\u2013284 (2001)","journal-title":"Bayreuth. Math. Schr."},{"key":"2028_CR17","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/s10107-006-0030-3","volume":"109","author":"M Laurent","year":"2007","unstructured":"Laurent, M.: Strengthened semidefinite programming bounds for codes. Math. Program. 109, 239\u2013261 (2007)","journal-title":"Math. Program."},{"issue":"1","key":"2028_CR18","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1007\/s10623-016-0216-5","volume":"84","author":"BM Litjens","year":"2017","unstructured":"Litjens, B.M., Polak, S.C., Schrijver, A.: Semidefinite bounds for nonbinary codes based on quadruples. Des. Codes Crypt. 84(1), 87\u2013100 (2017)","journal-title":"Des. Codes Crypt."},{"key":"2028_CR19","doi-asserted-by":"crossref","unstructured":"Nakata, M.: A numerical evaluation of highly accurate multiple-precision arithmetic version of semidefinite programming solver: SDPA-GMP, -QD and -DD. In: Proceedings of 2010 IEEE Multi-Conference on Systems and Control, pp. 29\u201334 (2010)","DOI":"10.1109\/CACSD.2010.5612693"},{"key":"2028_CR20","unstructured":"Norin, S., Zwols, Y.: Presentation at the BIRS Workshop on geometric and topological graph theory (13w5091) (2013). https:\/\/www.birs.ca\/events\/2013\/5-day-workshops\/13w5091\/videos\/watch\/201310011538-Norin.html"},{"key":"2028_CR21","unstructured":"Polak, S.C.: New methods in coding theory: error-correcting codes and the Shannon capacity. Ph.D. thesis, University of Amsterdam (2019)"},{"key":"2028_CR22","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-6804-6","volume-title":"The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions. Graduate Texts in Mathematics","author":"BE Sagan","year":"2001","unstructured":"Sagan, B.E.: The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions. Graduate Texts in Mathematics, vol. 203. Springer, New York (2001)"},{"key":"2028_CR23","unstructured":"Schaefer, M.: The graph crossing number and its variants: a survey. Electron. J. Comb. DS21 (2022)"},{"key":"2028_CR24","doi-asserted-by":"publisher","first-page":"2859","DOI":"10.1109\/TIT.2005.851748","volume":"51","author":"A Schrijver","year":"2005","unstructured":"Schrijver, A.: New code upper bounds from the Terwilliger algebra and semidefinite programming. IEEE Trans. Inf. Theory 51, 2859\u20132866 (2005)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"2028_CR25","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-9458-7","volume-title":"Linear Representations of Finite Groups. Springer Graduate Texts in Mathematics","author":"J-P Serre","year":"1977","unstructured":"Serre, J.-P.: Linear Representations of Finite Groups. Springer Graduate Texts in Mathematics. Springer, New York (1977)"},{"key":"2028_CR26","volume-title":"Graph Theory","author":"LA Sz\u00e9kely","year":"2016","unstructured":"Sz\u00e9kely, L.A.: Tur\u00e1n\u2019s brick factory problem: the status of the conjectures of Zarankiewicz and Hill. In: Gera, R., et al. (eds.) Graph Theory. Springer, New York (2016)"},{"key":"2028_CR27","doi-asserted-by":"publisher","first-page":"657","DOI":"10.1002\/jgt.3190170602","volume":"17","author":"DR Woodall","year":"1993","unstructured":"Woodall, D.R.: Cyclic-order graphs and Zarankiewicz\u2019s crossing-number conjecture. J. Graph Theory 17, 657\u2013671 (1993)","journal-title":"J. Graph Theory"},{"key":"2028_CR28","doi-asserted-by":"publisher","first-page":"137","DOI":"10.4064\/fm-41-1-137-145","volume":"41","author":"K Zarankiewicz","year":"1954","unstructured":"Zarankiewicz, K.: On a problem of P. Tur\u00e1n concerning graphs. Fundam. Math. 41, 137\u2013145 (1954)","journal-title":"Fundam. Math."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-023-02028-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-023-02028-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-023-02028-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,7]],"date-time":"2024-08-07T15:09:46Z","timestamp":1723043386000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-023-02028-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,20]]},"references-count":28,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2024,9]]}},"alternative-id":["2028"],"URL":"https:\/\/doi.org\/10.1007\/s10107-023-02028-1","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2023,11,20]]},"assertion":[{"value":"14 July 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 October 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 November 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}