# Do there exist sparse graphs with large crossing number?

Does there exist a sequence of graphs $\{ G_n \}$ such that

1. $G_n$ has $n$ vertices,
2. the number of edges of $G_n$ is $O(n)$, and
3. the crossing number of $G_n$ is $\Omega(n)$?

In particular, do random $k$-regular graphs satisfy this?

Motivation: the crossing number inequality gives a lower bound on the crossing number $cr(G)$, just in terms of the number of vertices $v$ and edges $e$. In particular, if $e \ge 4v$ then $$cr(G) \ge \frac{e^3}{64v^2}.$$ This is tight, up to a constant factor, meaning there are graphs whose crossing numbers are approximately this small. But this still raises the question of how large the crossing number can be, particularly for sparse graphs.

Take the following graph: start with the complete graph $K_5$, and replace every edge by $n/10$ paths of length $2$. The resulting graph has $n+5$ vertices, $2n$ edges, and crossing number $n^2/100$.

For random graphs with expected number of edges $e>10n$, Pach and Tóth showed that their crossing number is at least $e^2/4000$ almost surely.

Edit: In fact, the following graphs also satisfy the conditions 1-3, although they are not sparse: a complete graph with $2\sqrt{n}$ vertices together with $n-2\sqrt{n}$ isolated vertices has $n$ vertices, less than $2n$ edges, and more than $n^2/5 - O(n^{3/2})$ crossings.

(The constant $1/5$ in this last lower bound follows from the currently best known lower bound $0.8594 n^4/64 - O(n^3)$ on the crossing number of the complete graph by Klerk et al. They proved a lower bound for the complete bipartite graph, but a lower bound for $K_n$ follows by a straightforward double-counting argument.)

• Although Pach and Toth's paper deals with $G(n,p)$, it seems like their method would also prove a similar result for random regular graphs with $k$ large (since random regular graphs are usually good expanders, so will have bisection width linear in the number of vertices). – Kevin P. Costello Oct 3 '14 at 1:21

The complete bipartite graph $K_{3,n}$ has 3n edges and crossing number $cn^2$.

The crossing number of $C_3\times C_n$, the Cartesian product of the cycle $C_3$ and $C_n$, is given by $cr(C_3\times C_n)=n$ (see here), which satisfies your conditions: the number of vertices is $3n$ and the number of edges is $6n$.

In fact, it is conjectured that the crossing number of $C_m\times C_n$, the Cartesian product of the cycle $C_m$ and $C_n$, $$cr(C_m\times C_n)=(m-2)n,$$ which is known for $m\leq 6$ (See here), and for $n\geq m(m+1)$ (see here), which also satisfies your conditions: the number of vertices of $C_m\times C_n$ is $mn$ and the number of edges is $2mn$ for each fixed $m$.

Actually, even the crossing number of the random 3-regular graph on $n$ vertices has crossing number $\Theta(n^2)$. This follows from the lower bound obtained by Bollobás for the isoperimetric number of random regular graphs (European Journal of Combinatorics, Vol. 9 (1988), pp. 241-244); the random $k$-regular graph (for any fixed $k$) thus has large bisection width, guaranteeing a large (i.e., $\Theta(n^2)$) crossing number.

...and if you want regular, take any $k$-regular graph on $n$ vertices, and blow up every vertex by a factor of three. $3n$ vertices, $3k$-regular, and at least $\frac{1}{2}kn$ crossings.