比利时vs摩洛哥足彩
,
university of california san diego
****************************
combinatorics seminar
radoslav fulek
ist
the $\mathbb{z}_2$-genus of kuratowski minors
abstract:
a drawing of a graph on a surface is independently even if every pair of independent edges in the drawing crosses an even number of times. the $\mathbb{z}_2$-genus of a graph $g$ is the minimum $g$ such that $g$ has an independently even drawing on the orientable surface of genus $g$. an unpublished result by robertson and seymour implies that for every $t$, every graph of sufficiently large genus contains as a minor a projective $t\times t$ grid or one of the following so-called $t$-kuratowski graphs: $k_{3,t}$, or $t$ copies of $k_5$ or $k_{3,3}$ sharing at most $2$ common vertices. we show that the $\mathbb{z}_2$-genus of graphs in these families is unbounded in $t$; in fact, equal to their genus. together, this implies that the genus of a graph is bounded from above by a function of its $\mathbb{z}_2$-genus, solving a problem posed by schaefer and \v{s}tefankovi\v{c}, and giving an approximate version of the hanani-tutte theorem on surfaces.
host: andrew suk
january 12, 2018
2:00 pm
ap&m 6402
****************************