Vortrag von Dr. Sven Polak im Doctoral Seminar Mathematics „Semidefinite bounds for crossing numbers of K{m,n}
Computing the crossing number of the complete bipartite graph K_{m,n} is a long-standing open problem, going back to Turán in the 1940s. In this talk, we explain how to use semidefinite programming and representation theory to compute new lower bounds on the crossing number of K_{m,n}, extending a method from de Klerk et al. and the subsequent reduction by De Klerk, Pasechnik and Schrijver.
We exploit the full symmetry of the problem by developing a block-diagonalization of the underlying matrix algebra, and use it to improve bounds on several concrete instances. Some of our bounds are computed using a novel relaxation of the original semidefinite programming bound, by only requiring one small matrix block to be positive semidefinite.
Based on joint work with Daniel Brosch, arXiv:2206.02755
Veranstalter
Vortragende(r)
Dr. Sven Polak (Tilburg University)
Kontakt
Daniel Brosch (Daniel [dot] Brosch [at] aau [dot] at)
Ähnliche Veranstaltungen
