Skip to main content
5 of 5
added 60 characters in body
Michael Hardy
  • 1
  • 12
  • 85
  • 126

Is there a variant of the crossing lemma for multigraphs with arbitrary embedding?

Suppose $G$ is a graph embedded in the plane with $m=|E(G)|$ edges and $n=|V(G)|$ vertices. Suppose $\operatorname{sim}(G)$, the simplification of $G$ contains $ m' \gg 3n $ edges.
Call the set of edges corresponding to an edge $uv$ of $G$ the parallel set $p(uv)$ of $uv$. What is the maximum $r$ such that for some set $ W $ of edges of $\operatorname{sim}(G)$ the set $U$ of edges $e$ such that each edge of $p(e)$ is intersected by some edge of $p(f)$ for some $f \in W$ has size at least $r|W|$?

What is the maximum $r$ such that for some set $ W $ of vertices of $\operatorname{sim}(G)$ the set $U$ of edges $e \in \operatorname{sim}(G)$ such that each edge of $p(e)$ is intersected by some edge of $p(f)$ for some edge $f$ with at least one endpoint in $W$ has size at least $r|W|$?

Colloquially is crossing each edge of a parallel set much harder than crossing an edge of the simplification?

I found some stuff here but it has requirements on embedding https://arxiv.org/pdf/1801.00721.pdf

Hao S
  • 111
  • 2
  • 11