Printable PDF
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

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