printable pdf
比利时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

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