比利时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****************************