Graphs and digraphs behave quite differently, and many classical results for graphs are often trivially false when extended to general digraphs. Therefore it is usually necessary to restrict to a smaller family of digraphs to obtain meaningful results. One such very natural family is Eulerian digraphs, in which the in-degree equals out-degree at every vertex.
In this talk, we discuss several natural parameters for Eulerian digraphs and study their connections. In particular, we show that for any Eulerian digraph G with n vertices and m arcs, the minimum feedback arc set (the smallest set of arcs whose removal makes G acyclic) has size at least $m^2/2n^2+m/2n$, and this bound is tight. Using this result, we show how to find subgraphs of high minimum degrees, and also long cycles in Eulerian digraphs. These results were motivated by a conjecture of Bollob\'as and Scott.
Joint work with Ma, Shapira, Sudakov and Yuster