### 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

Abstract:
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.

See: http://math.rutgers.edu/seminars/allseminars.php?sem_name=Discrete%20Math