×

Improved bounds for the crossing numbers of \(K_{m,n}\) and \(K_{n}\). (English) Zbl 1111.05029

The main result of the paper is about the crossing number of the complete bipartite graph \(K_{n,7}\): \(\text{cr}(K_{n,7})\geq 2.1796n^2-4.5n\). The proof is based on a novel combination of arguments about graph drawings, quadratic programming, and the invariant theory of permutation groups. As usual in the theory of crossing numbers, improved lower bounds for the crossing number of any complete bipartite graph imply improved lower bounds on crossing numbers of larger complete bipartite or complete graphs. There is a well-known Zarankiewicz conjecture for the crossing number of complete bipartite graphs, and a related conjecture for the crossing number of complete graphs. Roughly speaking, the paper shows that 83% of the conjectured crossings are there, at least asymptotically. The best previous result was 80%.

MSC:

05C10 Planar graphs; geometric and topological aspects of graph theory
05C62 Graph representations (geometric and intersection representations, etc.)
90C22 Semidefinite programming
90C25 Convex programming
57M15 Relations of low-dimensional topology with graph theory
68R10 Graph theory (including graph drawing) in computer science