SFU Discrete Math Seminar: Jørgen Bang-Jensen

A digraph is semicomplete if it has no pair of non-adjacent vertices. A tournament is a semicomplete digraph with no directed 2-cycles. Tournaments form the most well studied class of directed graphs and a lot is known about their structure, ranging from very basic things you can teach a 1.st year student to extremely complicated things that take 100 pages or more to prove. I will survey some important results on connectivity and then give the main details of a recent proof, due to Pokrovskiy, that every 452k-strong tournament T is k linked, that is, for every choice of 2k vertices {x1, x2, ..., xk, y1, y2, ..., yk} there exist disjoint paths P1, P2, ..., Pk in T so that Pi is from xi to yi. Pokrovskiys beautiful proof of this result uses a very nice structural lemma which applies to all tournaments. If there is time, I will also say something more about the relation between semicomplete digraphs and tournaments.