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

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