***********************************
                * Princeton Discrete Math Seminar *
                ***********************************


Date: Thursday 11th October, 2.00 in Fine Hall 224
 
Speaker: Huang Hao (IAS)

Title: Extremal problems in Eulerian digraphs

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.


                       -----------

Next week: Shiva Kintali.

Anyone wishing to be added to or removed from this mailing list should
contact Paul Seymour (pds@math.princeton.edu)