Crossing number of complete bipartite graph

Question

I am looking for a proof of this inequality concerning the crossing number of a complete bipartite graph:

$$ \textrm{cr}(K_{m,n}) \le \left\lfloor\frac{n}{2}\right\rfloor\left\lfloor\frac{n-1}{2}\right\rfloor\left\lfloor\frac{m}{2}\right\rfloor\left\lfloor\frac{m-1}{2}\right\rfloor. $$

Thanks in advance.

Answer 1

I know this answer is almost 7 years late, but here is a sketch of a simple proof of Zarankiewicz's theorem on the upper bound for the crossing number of a complete bipartite graph -- I recently learnt this proof from Introduction to Graph Theory by Douglas West (namely, Example 6.3.15 in page 264). West gives a sketch, and I'll fill in some extra details.

For simplicity, let me assume both $m$ and $n$ are even (so that $n/2$ and $m/2$ are both integers). For the general case, you will have to use floors appropriately.

Arrange the evenly spaced $m/2$ on the positive $y$-axis, and the other $m/2$ on the negative $y$-axis. Similarly, place the $n/2$ points on the positive $x$-axis and $n/2$ points on the negative $x$-axis. Now, join every point on the $x$-axis to every point on the $y$-axis using a straight line. The resulting graph is clearly $K_{n, m}$. It remains to give an upper bound on the number of crossings in this drawing. It is clear that we can analyze the situation happening in one of the quadrants (say, positive $x$-axis and negative $y$-axis) and multiply the answer by $4$.

Analysis on the first quadrant. How many crossings do we see on the first quadrant? Let us call the points $x_{1}, ..., x_{n/2}$ on the positive $x$-axis and $y_{1}, y_{2}, ..., y_{m/2}$ on the $y$-axis, where we order these points in the usual order. We are connecting $x_i$ with $y_j$ for all $i$ and $j$. Here is the key question:

When does the line $L_{i, j} = \overline{x_i y_j}$ cross another line $L_{s,t}=\overline{x_s y_t}$?

Note that $L_{i, j}$ and $L_{s,t}$ cross if and only if either one of the inequalities below is satisfied:

• $i<s$ and $j>t$.
• $i>s$ and $j<t$

In all other cases, $L_{i, j}$ and $L_{s, t}$ do not cross. Thus, we see that approximately half of all the possible intersections between two different lines give rise to a proper crossing. It follows that the total number crossings happening in the positive quadrant is roughly at most: $$ \frac{1}{2}\cdot \binom{(m/2)\cdot (n/2)}{2} = \frac{1}{2}\cdot \binom{mn/4}{2} = \frac{1}{2} \cdot \frac{\left(\frac{mn}{4} \right)\left(\frac{mn}{4} -1\right)}{2} \approx \frac{1}{64} m^2 n^2 $$ Taking into account the other quadrants, we get that the crossing number of $G$ is roughly at most: $$ 4\cdot \left(\frac{1}{64} m^2 n^2\right) = \frac{1}{16} m^2 n^2 $$ as claimed.