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

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

math 269 - seminar in combinatorics

youngho yoo

texas a&m university (yyoo@tamu.edu)

erdős-pósa property in group-labelled graphs

abstract:

erdős and pósa proved in 1965 that every graph contains either $k$ vertex-disjoint cycles or a set of at most $o(k \log k)$ vertices intersecting every cycle. such an approximate duality does not hold for odd cycles due to certain projective-planar grids, as pointed out by lovász and schrijver, and reed showed in 1999 that these grids are the only obstructions to this duality. in this talk, we generalize these results by characterizing the obstructions in group-labelled graphs. specializing to the group $\mathbb{z}/m\mathbb{z}$ gives a characterization of when cycles of length $\ell \bmod m$ satisfy this approximate duality, resolving a problem of dejter and neumann-lara from 1988. we discuss other applications and analogous results for $a$-paths.

based on joint work with pascal gollin, kevin hendrey, o-joung kwon, and sang-il oum.

lutz warnke

october 8, 2024

2:00 pm

ap&m 7321

research areas

combinatorics

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