CSUN Algebra, Number Theory, and Discrete Mathematics Seminar

The genus $\mathrm{g}\left(G\right)$ of a graph $G$ is the minimum $g$ such that $G$ has an embedding on the orientable surface of genus $g$. The ${\mathbb{Z}}_2$-genus ${\mathrm{g}}_0\left(G\right)$ of a graph $G$ is the minimum $g$ such that $G$ has a drawing on the orientable surface of genus $g$ in which every pair of nonadjacent edges crosses an even number of times. Clearly, every graph $G$ satisfies ${\mathrm{g}}_0\left(G\right)\le \mathrm{g}\left(G\right)$. The Hanani–Tutte theorem states that ${\mathrm{g}}_0\left(G\right)=0$ if and only if $\mathrm{g}\left(G\right)=0$.

It has been a long-standing open problem whether the Hanani–Tutte theorem extends to surfaces other than the plane and projective plane, although the problem was first explicitly stated in print by Schaefer and Štefankovič in 2013. They conjectured that the Hanani–Tutte theorem extends to every orientable surface, that is, ${\mathrm{g}}_0\left(G\right)=\mathrm{g}\left(G\right)$ for every graph $G$.

We find a graph of genus 5 and its drawing on the orientable surface of genus 4 with every pair of nonadjacent edges crossing an even number of times. This shows that the Hanani–Tutte theorem cannot be extended to the orientable surface of genus 4 and refutes the conjecture of Schaefer and Štefankovič.

We complement our negative result by nearly-tight estimates of the ${\mathbb{Z}}_2$-genus for several well-known graph classes, including complete graphs and complete bipartite graphs. Along the way, we express the ${\mathbb{Z}}_2$-genus of a graph as a variant of the low-rank matrix completion problem.

Joint work with J. Kynčl.