Speaker: Etienne de Klerk

Joined work with John Maharry, Dima Pasechnik, Bruce Richter and Gelasio Salazar

Title: Progress on Tur\'an's brick factory problem

Abstract:

Consider the problem of drawing a complete bipartite graph $K_{n,m}$ in the plane such that as few edges as possible intersect. The minimum number of intersections for all drawings in the plane is called the crossing number of $K_{n,m}$. The problem of determining the crossing number of $K_{n,m}$ has been open for decades, and has only been settled for the case where $\min(m,n) < 7$. It sometimes called Tur\'an's brick factory= problem. In this talk we will describe some recent progress that can be obtained by relaxing the problem to a (non-convex) quadratic optimization problem over the simplex, and then approximating the latter problem by using a modern methodology for optimization of polynomials over compact semi-algebraic sets via semidefinite programming. In particular, we will present improved lower bounds on the crossing number of $K_{7,n}$, and discuss the implications.