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

Speaker: Alex Scott (University of Oxford)

Tomorrow, Thursday 8th December, 3:00 in Fine Hall 224.

Title: Invertibility of digraphs and tournaments

For an oriented graph D and a set X of vertices of D, the inversion of X 
in D is the digraph obtained from D by reversing the orientations of all 
edges with both endpoints in X.  The inversion number of D is the minimum 
number of inversions required to turn D into an acyclic digraph.

We answer several questions of Bang-Jensen, da Silva, and Havet: 

--(1)  We show that for each fixed k, it is possible to decide in quadratic 
time whether a tournament T has inversion number at most k. This exponent is 
optimal for all k.  

--(2) Building on their work, we prove their conjecture that for every k 
the problem is NP-complete for digraphs. 

--(3) We construct digraphs with inversion number equal to twice their 
cycle transversal number; and 

--(4) we disprove their conjecture concerning the inversion 
number of so-called `dijoin' digraphs.

Joint work with Emil Powierski, Michael Savery and Elizabeth Wilmer.


		----------------------------------


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