Extremal Problems in Eulerian Digraphs
|
Tue, 08/05/2012 14:30 |
Hao Huang (UCLA) |
Combinatorial Theory Seminar  |
L3 |
Graphs and digraphs behave quite diff erently, 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  , and this bound is tight. Using this result, we show how to fi nd subgraphs of high minimum degrees, and also long cycles in Eulerian digraphs. These results were motivated by a conjecture of Bollobás and Scott.
Joint work with Ma, Shapira, Sudakov and Yuster |
|||