Does the crossing number of a subgraph give a lower bound for the crossing number of a graph?

115 Views Asked by At

I thought of this fairly trivial inequality when thinking about the crossing number of graphs. As the title says, if you find a subgraph with a known crossing number in some graph G (say $Q_4$ for example) does this imply that $$cr(G) \geq cr(S)$$ where $S$ is the subgraph we found in some graph G? Another further extension I thought of was $$cr(G) \geq ncr(S)$$ where n is the number of S subgraphs found. Of course some crossings might be double counted so the last inequality won't always hold.

I came up with this while trying to prove $cr(Q_5) = 56$ as I can find 7 subgraphs in $Q_5$ isomorphic to $Q_4$. Since the crossing number of $Q_4$ is known to be 8 doesn't this say something about $cr(Q_5)$?

I apologize if this is all completely trivial.

1

There are 1 best solutions below

0
On BEST ANSWER

The first inequality is correct: given an embedding for $G$ with a number of crossings, you can use the same embedding for $S$ by removing edges, which doesn't increase the number of crossings.

However, I don't understand how you count the number of copies of $S$ in $G$. If you count all copies, then your claim is incorrect. For example, $cr(K_5)=1$ and $K_n$ has $n \choose 5$ copies of $K_5$, but $cr(K_n)$ is not of the order of $n^5$ (it is $O(n^4)$). More generally, the number of copies of a subgraph could be exponential but the crossing number is always at most quadric.