Department of Mathematics,
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
****************************