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%.
Reviewer: László A. Székely (Columbia)
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 |