The long standing Zarankiewicz's conjecture states that the crossing number cr(Km,n) of the complete bipartite graph is Z(m,n):= [m/2][m-1/2][n/2][n-1/2]. Using flag algebras we show that cr(Kn,n) ≥ 0.9118 • Z(n, n) + o(n4). We also show that the rectilinear crossing number cr-(Kn,n) of Kn,n is at least 0.987 • Z(n,n) + o(n4). Finally, we show that if a drawing of Kn,n has no K3,4 that has exactly two crossings, and these crossings share exactly one vertex, then it has at least Z(n,n) + o(n4) crossings. This is a local restriction inspired by Turán type problems that gives an asymptotically tight result.

Borrowing László Székely's lively expression, we show that Hill's conjecture is “asymptotically at least $98.5\%$ true.” This long-standing conjecture states that the crossing number cr$(K_n)$ of the complete graph $K_n$ is $H(n) := \frac{1}{4}{\lfloor\frac{n}{2}\rfloor}{\lfloor\frac{n-1}{2}\rfloor}{\lfloor\frac{n-2}{2}\rfloor}{\lfloor\frac{n-3}{2}\rfloor}$ for all $n\ge 3$. This has been verified only for $n\le 12$. Using the flag algebra framework, Norin and Zwols obtained the best known asymptotic lower bound for the crossing number of complete bipartite graphs, from which it follows that for every sufficiently large $n$, cr$(K_n) > 0.905\, H(n)$. Also using this framework, we prove that asymptotically cr$(K_n)$ is at least $0.985\, H(n)$. We also show that the spherical geodesic crossing number of $K_n$ is asymptotically at least $0.996\, H(n)$.

Let $D$ be a knot diagram, and let ${\mathcal D}$ denote the set of diagrams that can be obtained from $D$ by crossing exchanges. If $D$ has $n$ crossings, then ${\mathcal D}$ consists of $2^n$ diagrams. A folklore argument shows that at least one of these $2^n$ diagrams is unknot, from which it follows that every diagram has finite unknotting number. It is easy to see that this argument can be used to show that actually ${\mathcal D}$ has more than one unknot diagram, but it cannot yield more than $4n$ unknot diagrams. We improve this linear bound to a superpolynomial bound by showing that at least $2^{\sqrt[3]{n}}$ of the diagrams in ${\mathcal D}$ are unknot. We also show that either all the diagrams in ${\mathcal D}$ are unknot or there is a diagram in ${\mathcal D}$ that is a diagram of the trefoil knot.

Let $K, L$ be convex sets in the plane. For normalization purposes, suppose that the area of $K$ is 1. Suppose that a set $K_n$ of $n$ points is chosen independently and uniformly over $K$, and call a subset of $K$ a hole if it does not contain any point in $K_n$. It is shown that with high probability the largest area of a hole homothetic to $L$ is $(1+o(1)) \log{n}/n$. We also consider the problems of estimating the largest area convex hole and the largest area of a convex polygonal hole; with vertices in $K_n$. For these two problems we give an answer that is asymptotically tight within a factor of 4.

In the influential paper in which he proved that every graph with $m$ edges can be embedded in a book with $O({m}^{1/2})$ pages, Malitz proved the existence of $d$-regular $n$-vertex graphs that require $\Omega(\sqrt{d}n^{\frac{1}{2}-\frac{1}{d}})$ pages. In view of the $O({m}^{1/2})$ bound, this last bound is tight when $d > \log{n}$, and Malitz asked if it is also tight when $d< \log{n}$. We answer negatively to this question by showing that there exist $d$-regular graphs that require $\Omega(n^{\frac{1}{2}-\frac{1}{2(d-1)}})$ pages. In addition, we show that the bound $O({m}^{1/2})$ is not tight either for most $d$-regular graphs by proving that for each fixed $d$, with high probability the random $d$-regular graph can be embedded in $o({m}^{1/2})$ pages. We also give a simpler proof of Malitz's $O({m}^{1/2})$ bound and improve the proportionality constant.

A book with $k$ pages consists of a straight line (the spine) and $k$ half-planes (the pages), such that the boundary of each page is the spine. If a graph is drawn on a book with $k$ pages in such a way that the vertices lie on the spine, and each edge is contained in a page, the result is a k-page book drawing (or simply a $k$-page drawing). The $k$-page crossing number $\nu_k(G)$ of a graph $G$ is the minimum number of crossings in a $k$-page drawing of $G$. In this paper we investigate the $k$-page crossing numbers of complete graphs. We use semidefinite programming techniques to give improved lower bounds on $\nu_k(K_n)$ for various values of $k$. We also use a maximum satisfiability reformulation to obtain a computer-aided calculation of the exact value of $\nu_k(K_n)$ for several values of $k$ and $n$. Finally, we investigate the best construction known for drawing $K_n$ in $k$ pages, calculate the resulting number of crossings, and discuss this upper bound in light of the new results reported in this paper.

Around 1958, Hill conjectured that the crossing number CRg(Kn) of the complete graph KKn is Z(n):=1/4 ⌊ n/2 ⌋ ⌊(n-1)/2⌋ ⌊ (n-2)/2 ⌋ ⌊ (n-3)/2 ⌋ and provided drawings of Kn with exactly Z(n) crossings. Towards the end of the century, substantially different drawings of Kn with Z(n) crossings were found. These drawings are 2-page book drawings, that is, drawings where all the vertices are on a line l (the spine) and each edge is fully contained in one of the two half-planes (pages) defined by l. The 2-page crossing number of Kn, denoted by ν2(Kn), is the minimum number of crossings determined by a 2-page book drawing of Kn. Since CRG(Kn) ≤ ν2(Kn) and ν2(Kn) ≤ Z(n), a natural step towards Hill's Conjecture is the weaker conjecture ν2(Kn) = Z(n), that was popularized by Vrt'o. In this paper we develop a novel and innovative technique to investigate crossings in drawings of Kn, and use it to prove that ν2(Kn) = Z(n). To this end, we extend the inherent geometric definition of k-edges for finite sets of points in the plane to topological drawings of Kn. We also introduce the concept of ≤≤k-edges as a useful generalization of ≤k-edges. Finally, we extend a powerful theorem that expresses the number of crossings in a rectilinear drawing of Kn in terms of its number of k-edges to the topological setting.

It has been long conjectured that the crossing number $\Cr(K_{m,n})$ of the complete bipartite graph $K_{m,n}$ equals the Zarankiewicz number $Z(m,n):= \floor{\frac{m-1}{2}} \floor{\frac{m}{2}} \floor{\frac{n-1}{2}} \floor{\frac{n}{2}}$. Another longstanding conjecture states that the crossing number $\Cr(K_n)$ of the complete graph $K_n$ equals $Z(n):=\frac{1}{4}\smallfloor{\frac{n}{2}} \smallfloor{\frac{n-1}{2}} \smallfloor{\frac{n-2}{2}}\smallfloor{\frac{n-3}{2}}$. In this paper we show the following improved bounds on the asymptotic ratios of these crossing numbers and their conjectured values: \begin{itemize} \item[(i)] for each fixed $m\ge 9$, $\lim_{n\to\infty} \Cr(K_{m,n})/Z(m,n) \ge 0.83m/(m-1)$; \item[(ii)] $\lim_{n\to\infty} \Cr(K_{n,n})/Z(n,n) \ge 0.83$; and \item[(iii)] $\lim_{n\to\infty} \Cr(K_{n})/Z(n) \ge 0.83$. \end{itemize} The previous best known lower bounds were $0.8m/(m-1), 0.8$, and $0.8$, respectively. These improved bounds are obtained as a consequence of the new bound $\Cr(\ksn) \ge 2.1796n^2 - 4.5n$. To obtain this improved lower bound for $\Cr(\ksn)$, we use some elementary topological facts on drawings of $K_{2,7}$ to set up a quadratic program on $6!$ variables whose minimum p satisfies $\Cr(\ksn) \ge (p/2)n^2 - 4.5n$, and then use state-of-the-art quadratic optimization techniques combined with a bit of invariant theory of permutation groups to show that $p \ge 4.3593$.