I asked this question over at MathOverflow, but thinking about it a little more I think it is a more natural fit here.

Let $G$ be a directed graph with $n$ vertices and $m$ edges such that every directed cycle in $G$ has length at least $m/k$. An arcset of $G$ is defined as a set of edges $X$ whose removal from $G$ leaves an acyclic graph. What is the best known bound on the size of the smallest such $X$? The best I have been able to find in the literature is a bound $|X| \leq O(k \log k \log \log k)$ due to Seymour (see 1.4 here: https://link.springer.com/article/10.1007/BF01200760 ).

Meanwhile, the best known worst-case lower bound is $|X| \geq O(k \log k)$, which can be obtained by taking an undirected expander graph and orienting the edges appropriately. Has this gap of $\log \log k$ been closed?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.