Discrete Mathematics and Optimization Seminar

---

FREDERIC HAVET
CNRS and INRIA Sophia-Antipolis
Monday October 6th at 4.30pm
Burnside 1205



Title. Median order in tournaments.

Abstract. A median order in a digraph is an ordering v_1, v_2,..., v_n that minimizes the number of arcs (v_i,v_j) with i>j.
A tournament is an orientation of the arcs of a complete undirected graph. In this talk, median orders are used to prove results
about the two following conjectures. The first one due to Seymour asserts that every digraph contains a vertex
whose second outneighborhood larger or equal to its (first) outneighborhood. The second one due to Sumner states that a tournament
of order 2n-2 contains (as a subdigraph) every oriented tree of order n. We prove Seymour's conjecture for tournaments and
Sumner's for arborescences. We also prove that a tournament of order 3.5n contains (as a subdigraph) every oriented tree of order n.