13
$\begingroup$

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.

$\endgroup$
17
$\begingroup$

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.)

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ 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). $\endgroup$ – Kevin P. Costello Oct 3 '14 at 1:21
9
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
5
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$
5
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

...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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.