Directed graphs without short cycles
| dc.creator | Fox, Jacob | |
| dc.creator | Keevash, Peter | |
| dc.creator | Sudakov, Benny | |
| dc.date | 2008-09-26 | |
| dc.date.accessioned | 2026-07-07T10:05:49Z | |
| dc.date.available | 2026-07-07T10:05:49Z | |
| dc.description | For a directed graph $G$ without loops or parallel edges, let $β(G)$ denote the size of the smallest feedback arc set, i.e., the smallest subset $X \subset E(G)$ such that $G \sm X$ has no directed cycles. Let $γ(G)$ be the number of unordered pairs of vertices of $G$ which are not adjacent. We prove that every directed graph whose shortest directed cycle has length at least $r \ge 4$ satisfies $β(G) \le cγ(G)/r^2$, where $c$ is an absolute constant. This is tight up to the constant factor and extends a result of Chudnovsky, Seymour, and Sullivan. This result can be also used to answer a question of Yuster concerning almost given length cycles in digraphs. We show that for any fixed $0 < θ< 1/2$ and sufficiently large $n$, if $G$ is a digraph with $n$ vertices and $β(G) \ge θn^2$, then for any $0 \le m \le θn-o(n)$ it contains a directed cycle whose length is between $m$ and $m+6 θ^{-1/2}$. Moreover, there is a constant $C$ such that either $G$ contains directed cycles of every length between $C$ and $θn-o(n)$ or it is close to a digraph $G'$ with a simple structure: every strong component of $G'$ is periodic. These results are also tight up to the constant factors. | |
| dc.identifier | https://arxiv.org/abs/0809.4690 | |
| dc.identifier | http://arxiv.org/abs/0809.4690 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/170122 | |
| dc.subject | Combinatorics | |
| dc.title | Directed graphs without short cycles | |
| dc.type | text |