Seymour's Second Neighborhood Conjecture

Special cases

Although SSNC has not been proven yet for all oriented graphs, there exist several proofs of special families of oriented graphs. Below, you will find a couple of articles with such proofs. To read a summary of and comments on the article, please click on the links below to fold out the menu. If you want to read the article itself, you can click on the PDF logo next to the author's name.

A Combinatorial Proof of Seymour's Conjecture for Regular Oriented Graphs with Regular Outsets O'a and O''a, Lester Mackey

Via proof by contradiction, Mackey proves SSNC for regular oriented graphs G = (V,E) with regular sets O'a and O''a for some a ∈ V. To this end, he defines the outset and the second degree outset of a vertex. The outset of a vertex a, denoted O'a, is the set of all vertices to which an out-going edge extends from a. The second degree outset, O''a, may be defined as the union of the outsets of all x in O'a minus O'a. In his proof, Mackey applies an inventive combinatorial method involving estimations of the outset and second degree outset of a vertex.

Squaring a Tournament: A Proof of Dean's Conjecture, David Fisher

In a "round robin tournament" each team plays every other team exactly once. Assuming no ties, for each pair of teams i and j, either i beats j or j beats i, but not both. Therefore, a tournament T is an oriented graph where either (vi,vj) ∈ T or (vj,vi) ∈ T, but not both. This special case of SSNC is also known as Dean's Conjecture. Dean and Latka [1] verified the conjecture for tournaments whose minimum out-degree is five or less. They also verified the conjecture for regular and almost regular tournaments. In his article Squaring a Tournament: A Proof of Dean's Conjecture, David Fisher proves Dean's Conjecture for all possible tournaments. To this end, he introduces a (probability) density f on an oriented graph D: each vertex gets a non-negative value in such a way that the sum of all values is 1. (Let the probability of a set be the sum of the probability of its members.) A density w is winning if w(ID(vi)) ≥ w(OD(vi)) for all vertices vi, where ID is the set of vertices that beat vi and OD is the set of vertices that vi beats. In other words: for any node vi, a random vertex picked from a winning density is at least as likely to beat vi as it is to lose to vi. Now the question rises: do all oriented graphs have winning densities? To confirm this question, Fisher gives a – in my opinion – beautiful proof using Farkas' Lemma. This lemma is primarily used in linear programming and therefore it is quite fascinating for Fisher to use it here. A simple corollary of the fact that every oriented graph has a winning density w is that every oriented graph has a losing density l, too. (For a losing density l(ID(vi)) ≤ l(OD(vi)) holds for all vertices vi.) What follows in Fisher's proof is a short analytical proof which is easy to understand. Fisher makes use of two lemmata. One of them does not generalise from tournaments to all oriented graphs and that is why Fisher's method cannot prove SSNC in general. References: [1]   N. Dean and B. Latka, Squaring a tournament – an open problem, Congre. Numer., 109 (1995), 73–80. N.B.: Frédéric Havet and Stéphan Thomassé prove Dean's Conjecture in an even shorter way, using so-called median orders of tournaments. Their method has several other applications in graph theory (not necessarily of any importance to SSNC). A summary of their article Median Orders of Tournaments: A Tool for the Second Neighborhood Problem and Sumner's Conjecture can be found here.

Variations on Seymour's Conjecture, Kelly Anderson, Catherine Nightingale, and Monique Richardson

Anderson, Nightingale, and Richardson verify SSNC for six different families of oriented graphs: Acyclic directed graphs: An acyclic directed graph is a directed graph containing no cycles. It is proven that in any acyclic directed graph, there exists a vertex with out-degree 0. To finish the proof of SSNC for acyclic directed graphs is mere child's play. Cayley graphs with additive generators: The infinite Cayley line with additive generators is a directed graph determined by a set of generators Γ = {g1,g2,...gk}, where gi is an integer and 0 ∉ Γ. The vertices of the graph correspond to the elements of the integers, and whenever gi + a = b (where a and b are integers), an edge is drawn from a to b. In the article it is proven that all vertices in an infinite Cayley line with additive generators satisfy SSNC. A Cayley graph modulo n, C(Γ,n), is defined for a subset Γ of V = {0,1,2,...,n - 1} as being the directed graph with vertex set V, in which there is an edge from u to u+e if and only if e ∈ Γ. Out-regular directed graphs: SSNC is proven for k-out regular oriented graphs for k < 4. The proofs for k = 1 and k = 2 are not hard to understand. For k = 3 and k = 4, several cases are considered, such that the union of the cases form the complete proof. The authors of the article believe that similar types of arguments as used for the 3-out-regular and 4-out-regular oriented graphs will work to prove the conjecture that SSNC holds for all out-regular oriented graphs. k-out-regular bipartite graphs: An oriented bipartite graph is a directed graph whose vertex set can be partitioned into two disjoint, independent sets called partite sets. An easy argument shows that all vertices of every k-out-regular oriented bipartite graph satisfy SSNC. Pinwheel graphs: Kn denotes the complete graph on a vertex set {1,2,...,n}. The line graph L(G) of a graph G is a graph whose vertex set is the edge set of G. Two vertices of L(G) are adjacent if the corresponding edges share a vertex in G. A triplet in L(Kn), the line graph of Kn, is the subgraph induced by three vertices ab, ac and bc, where a,b,c ∈ {1,2,...,n}. PWCn denotes a pinwheel graph, which is a directed line graph of the clique on n elements where every triplet forms a directed 3-cycle. It is not hard to see that the out-degree of a random vertex uv is equal to n - 2 and that n - 2 is less than or equal to the numbers of vertices at distance two of this vertex uv. Hence, all vertices in any pinwheel graph PWCn satisfy SSNC. Cartesian products of directed graphs: The Cartesian product of directed graphs G and H, written G ⊗ H, is the graph with vertex set V(G) × V(H) specified by putting an edge from (u,v) to (u',v') (where (u,v), (u',v') ∈ G ⊗ H) if and only if (1) u = u' and vv' ∈ E(H), or (2) v = v' and uu' ∈ E(G). G and H are known as the factor graphs of the Cartesian product. Anderson, Nightingale, and Richardson prove that if both factor graphs of a Cartesian product each have at least one vertex that satisfies SSNC, there will be at least one vertex in the Cartesian product which satisfies SSNC. N.B.: The notation for a Cartesian product, G ⊗ H, is my own notation. Anderson, Nightingale, and Richardson use a square in their article, but if I used that same symbol on this website, people might get the wrong impression that their computer cannot recognise the symbol. Finally, the three authors of the article show that if SSNC holds for strong oriented graphs, then it holds for all oriented graphs.