Rutgers Discrete Mathematics Seminar

Title: Extremal problems in Eulerian digraphs

Speaker: Hao Huang, IAS

Date: Tuesday, October 30, 2012 2:00pm

Location: Hill Center, Room 525, Rutgers University, Busch Campus, Piscataway, NJ


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 Bollobas and Scott. Joint work with Ma, Shapira, Sudakov and Yuster.