比利时vs摩洛哥足彩
,
university of california san diego
****************************
math 269 - combinatorics
blair sullivan
princeton university
feedback arc sets and girth in digraphs
abstract:
given a directed graph $g$ with girth at least $m+1$ (and no parallel edges), let $\beta(g)$ denote the size of the smallest subset $x \subseteq e(g)$ so that $g \setminus x$ has no directed cycles, and let $\gamma(g)$ be the number of non-edges. prior joint work with maria chudnovsky and paul seymour showed that when $m = 3$, $\beta(g) \leq \gamma(g)$, and we conjectured $\beta(g) \leq \frac{1}{2}\gamma(g)$. can one say anything stronger if $m > 3$? in this talk, i will discuss a new conjecture giving a ratio between $\beta(g)$ and $\gamma(g)$, namely $\beta(g) \leq \frac{2}{m^2-m-1}\gamma(g)$, for $m \geq 3$. the talk will also cover two new results in this direction: the bound $\beta(g) \leq \frac{1}{3}\gamma(g)$ when $m=4$, and for circular interval graphs, a generalization of previous methods which gives a new bound for all $m$.
host: fan chung graham
october 16, 2007
4:00 pm
ap&m 7321
****************************