Extremal Problems in Eulerian Digraphs
Graphs and digraphs behave quite differently and many natural results for graphs are often trivially false for general digraphs. It is usually necessary to consider restricted families of digraphs to obtain meaningful results. One such very natural family is Eulerian digraphs, i.e., digraphs in which in-degree of every vertex equals its out-degree. We will discuss several natural parameters for Eulerian digraphs and study their connections. In particular, we show that for any Eulerian digraph with n vertices and m arcs, the minimum feedback arc set (that is a smallest set of arcs whose removal makes the digraph acyclic) has size at least m^2/2n^2+m/2n, and this bound is optimal. Using this result we show how to find subgraphs of high minimum in- and out-degree and also long cycles in Eulerian digraphs. These results were motivated by a conjecture of Bollobas and Scott. Joint work with Huang, Shapira, Sudakov and Yuster.