Crossing sequences

Definitions and mathematical statement

For an integer $g\ge0$, let $\Sigma_g$ be the closed orientable surface of genus $g$, with $\Sigma_0$ the sphere. For $g\ge1$, let $N_g$ be the closed nonorientable surface obtained as a connected sum of $g$ projective planes, and put $N_0$ equal to the sphere solely to index a sequence from zero.

For a finite graph $G$ and a surface $S$, its crossing number $\operatorname{cr}_S(G)$ is the least number of transverse crossings in a drawing of $G$ on $S$. Vertices are distinct, edge interiors avoid vertices, each edge is a simple arc, no three interiors meet at a point, and coincident edge segments are forbidden. In particular, crossing number zero means that the graph embeds in the surface.

Fix any integer $m\ge0$ and any finite strictly decreasing sequence of nonnegative integers \[ a_0>a_1>\cdots>a_{m-1}>a_m=0, \] where for $m=0$ the sequence is just $(0)$. The orientable conjecture asks for a finite graph $G$ satisfying $\operatorname{cr}_{\Sigma_i}(G)=a_i$ for every $0\le i\le m$. The nonorientable conjecture asks the same with $N_i$ in place of $\Sigma_i$, possibly using a different graph.

Equality requires both a drawing with exactly the prescribed number and proof that fewer crossings are impossible. Once zero is reached, all subsequent surface crossing numbers are automatically zero by adding unused handles or crosscaps. No convexity condition or prescribed size of successive decreases is assumed.

Short English statement

Can every finite strictly decreasing sequence ending in zero occur as a graph’s crossing numbers on successive orientable surfaces, and likewise on successive nonorientable surfaces?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3322 (OPG-1812), OpenGarden. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Crossing sequences. Original problem and discussion. http://www.openproblemgarden.org/op/crossing_sequences.