Printable PDF
##### Department of Mathematics, University of California San Diego

****************************

## The $\mathbb{Z}_2$-genus of complete bipartite graphs

##### Abstract:

A drawing of a graph on a surface is {\em independently even} if every pair of nonadjacent edges in the drawing crosses an even number of times. The strong Hanani-Tutte theorem states that a graph admitting an independently even drawing in the plane must be planar. The {\em genus} $g(G)$ of a graph $G$ is the minimum $g$ such that $G$ has an embedding on the orientable surface $M_g$ of genus $g$. The {\em $\mathbb{Z}_2$-genus} of a graph $G$, denoted $g_0(G)$, is the minimum $g$ such that $G$ has an independently even drawing on the orientable surface of genus $g$. Clearly, every graph $G$ satisfies $g_0(G) \leq g(G)$, and the strong Hanani-Tutte theorem states that $g_0(G) = 0$ if and only if $g(G) = 0$. Although there exist graphs $G$ for which the values of $g(G)$ and $g_0(G)$ differ, several recent results suggest that these graph parameters are closely related. We provide further evidence of their similarity. For complete bipartite graphs $K_{n,m}$ with $n \geq 3$, we prove the following: $$g_0(K_{n,m}) \geq \lceil \frac{1}{2} \left( \lceil \frac{(n-2)(m-2)}{2} \rceil - (n-3) \right) \rceil$$ The value of $g(K_{n,m})$ was determined by Ringel in 1965, and equals $\lceil \frac{(n-m)(m-2)}{4} \rceil$. Joint work with J. Kyncl.

Host: Jacques Verstraete

### AP&M 6402

****************************