Abstract

Median Orders of Tournaments

Mike Neiman
Mon Nov 1 at 1:10pm in the Graduate Student Lounge

I will be talking about a paper by Havet and Thomasse. A median order of a tournament T is a total order of its vertices that has maximum intersection with T. I will discuss median orders and use them to prove some results about tournaments, namely:

(1) Every tournament contains a vertex whose second neighborhood is at least as large as its first neighborhood.

(2) Some partial results for Sumner's conjecture: every tournament of order 2n-2 contains every oriented tree of order n.