printable pdf
比利时vs摩洛哥足彩 ,
university of california san diego

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

math 269 - combinatorics

radoslav fulek

ist austria

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

november 27, 2018

2:00 pm

ap&m 6402

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