Seymour's Second Neighborhood Conjecture

Other results

The method of median orders

As I already mentioned in my comments on David Fisher's article on the page Special cases, Frédéric Havet and Stéphan Thomassé give a short constructive proof of Dean's Conjecture in their article Median Orders of Tournaments: A Tool for the Second Neighborhood Problem and Sumner's Conjecture. An abstract of this article can be found here and clicking on this link will provide you with the entire article. Below, I will discuss the contents of the article. I will do this very briefly, since the authors use a terminology differing from that used on the rest of this website. If you want to know the details of the proofs, I recommend fully reading the article.

A median order of a tournament T is a linear extension of an acyclic oriented subgraph of T, maximal with respect to its numbers of arcs. Determining a median order of an oriented graph is NP-hard and the complexity for tournaments is still unknown. Although the notion of median order has seldom been used as a tool in tournament theory, it appears that median orders provide a very powerful inductive method, as Havet and Thomassé demonstrated in their article: using median orders they prove Dean's Conjecture as well as a special case of Sumner's Conjecture, which will be explained below.

Recall that Dean's Conjecture states that every tournament contains a vertex whose second out-neighbourhood is at least as large as its first out-neighbourhood (i.e. Dean's Conjecture is the special case of SSNC for tournaments). The authors not only prove Dean's Conjecture, but they also exhibit two vertices that meet this requirement, provided that the tournament has no dominated vertices, which are vertices with no out-going edges.

A second application of median orders is that every tournament of order 2n - 2 contains every arborescence of order n > 1. An arborescence is an oriented tree in which one vertex, called the root, has in-degree 0 and the remaining vertices have in-degree 1. This is a particular case of Sumner's Conjecture: every tournament of order 2n - 2 contains every oriented tree of order n > 1. Havet and Thomassé were also able to obtain an upper bound of (7n - 5)/2 in place of 2n - 2. Compared with the upper bound that Häggkvist and Thomason found in 1991, 12n, this was a huge improvement, which underlines the efficiency of the method of median orders.

Properties of counterexamples to SSNC

James Brantner, Greg Brockman, Bill Kay, and Emma Snively wrote an article called Contributions to Seymour's second neighborhood conjecture. In this article, they reverse course and explore the necessary properties of a (minimal) counterexample to SSNC. I did not read the entire article myself, but if you are interested in these properties, you can find the article here.