{'fraction_non_alphanumeric': 0.06327009583414825, 'fraction_numerical': 0.01711324075884999, 'mean_word_length': 3.6955922865013773, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Contributions to Seymour's Second Neighborhood Conjecture

Let D be a simple digraph without loops or digons. For any v in V(D) let N_1(v) be the set of all nodes at out-distance 1 from v and let N_2(v) be the set of all nodes at out-distance 2. We provide sufficient conditions under which there must exist some v in V(D) such that |N_1(v)| is less than or equal to |N_2(v)|, as well as examine properties of a minimal graph which does not have such a node. We show that if one such graph exists, then there exist infinitely many strongly-connected graphs having no such vertex.


Introduction
For the purposes of this article, we consider only simple nonempty digraphs (those containing no loops or multiple edges and having a nonempty vertex set), unless stated otherwise. We also require that our digraphs contain no digons, that is, if D is a digraph then (u, v) ∈ E(D) ⇒ (v, u) / ∈ E(D). If i is a positive integer, we denote the i th neighborhood of a vertex u in D by N i,D (u) = {v ∈ V (D)|dist D (u, v) = i}, where dist D (u, v) is the length of the shortest directed path from u to v in D (if there is no directed path from u to v, we set dist D (u, v) = ∞). If D is clear from context, we simply write N i (u) and dist (u, v). We also may wish to consider the i th in-neighborhood of a vertex N −i (u) = {v ∈ V (D)|dist(v, u) = i}. In addition, if V ⊆ V (D), we let D[V ] be the subgraph of D induced by V .
Graph theorists will be familiar with the following conjecture due to Seymour (see [3]), now more than a decade old: In 1995, Dean [3] conjectured this to be true when D is a tournament. Dean's Conjecture was subsequently proven by Fisher [5] in 1996. Further, in their 2001 paper Kaneko and Locke [6] showed Conjecture 1.1 to be true if the minimum outdegree of vertices in D is less than 7, and Cohn, Wright, and Godbole [2] showed that it holds for random graphs almost always. And finally, in 2007 Fidler and Yuster [4] proved that Conjecture 1.1 holds for graphs with minimum out-degree |V (D)|−2, tournaments minus a star, and tournaments minus a sub-tournament. While over the years there have been several attempts at a proof of Conjecture 1.1, none of these have yet been successful.
For completeness, we introduce the related Caccetta-Häggkvist conjecture [1], which was posed in 1978: . If D is a directed graph with minimum outdegree at least |V (D)|/k, then D has a directed cycle of length at most k. We do not seek to prove Conjecture 1.1 in this paper. Rather, we prove the conjecture for various classes of graphs. We then take a different tack and provide conditions that must be satisfied by any appropriately-defined minimal counterexample to Seymour's Second Neighborhood Conjecture. This provides tools with which the conjecture can be approached; in one direction it may aid in showing the nonexistence of such a graph, while in the other direction we restrict the search space of possible counterexamples.

Definitions
We begin our investigation by defining some useful terms.
Definition 2.1. Suppose that D is digraph and u ∈ V (D). We say that u is satisfactory if |N 1 (u)| ≤ |N 2 (u)|. Also, u is a sink if |N 1 (u)| = 0. Note that a sink is trivially satisfactory.  Also define A s,D (u) = |N 1 (u)| − |N 2 (u)| to be the anti-satisfaction of u. As usual, if G is clear from context, we simply write A s (v). Notice that u is satisfactory if and only if A s (u) ≤ 0.
Definition 2.4. Again let D be a directed graph. Recall that a transitive triangle T is a directed graph on three nodes a, b, c such that (a, b), (a, c), (b, c) ∈ E(T ). If (u, v) ∈ E(D), we say that edge (u, v) is the base of a transitive triangle if u and v share a common first neighbor; that is, Base Figure 1 -Demonstration of an edge that is the base of a transitive triangle We now have the tools to delve into our results.

Directed cycles and underlying girth
In this section we show that certain classes of graphs satisfy Seymour's Second Neighborhood Conjecture. The following theorem shows that directed cycles are necessary for a graph to be a counterexample to the conjecture. Proof. Let D be a directed graph, and suppose that D contains no satisfactory vertices. Then D has no sink, as noted in Definition 2.1. It is a well-known fact that a graph with no sinks has a directed cycle. We include the standard proof, however, since the same technique will be useful to us later: The following theorem provides another sufficient condition for a graph to contain a satisfactory vertex: Proof. Let v 0 ∈ V (D) have the minimal out-degree in D. If |N 1 (v 0 )| = 0, then v 0 is a sink and hence a satisfactory vertex. Otherwise, let v 1 ∈ N 1 (v 0 ). By construction, we have that Remark. Recall that the girth of a undirected graph is the length of its shortest cycle. Theorem 3.2 shows that any counterexample to Conjecture 1.1 must have underlying girth of exactly 3.

Minimal Criminals
To this point, we have been showing that classes of graphs satisfy Conjecture 1.1. In this section we reverse course and explore necessary properties of the minimal criminal graphs of A from Definition 2.2. If Seymour's Second Neighborhood Conjecture is true, then our goal should be to derive such strong constraints on the graphs of A that a contradiction is obtained. On the other hand, if the conjecture is false, then our goal is to find necessary or sufficient conditions for a graph to be in A ; we provide a number of necessary conditions here. Proof of 3: We see that |N 2,Z (u)| ≥ |N 2,M (u)|, since otherwise A s,Z (u) ≤ 0 and u is not satisfactory in Z, a contradiction. Consider now X = N 2,Z (u) \ N 2,M (u). We note that X ⊆ {v}, since v is the only vertex that could have been added to u's second neighborhood in Z (Case 1 in Figure 3). Thus we see that  (u, y)). If |N 2,M (u) \ N 2,Z (u)| = 0, then for z ∈ Z, we therefore have a path of length 2 from u to z in Z, and considering this path in M yields a path from u to z avoiding e. And finally, if |N 2,M (u) \ N 2,Z (u)| = 1, then we have a path of length 2 from u to z in Z for all but 1 vertex in Z, and as before we have a corresponding path from u to z avoiding e. But in this case, there is a path of length 2 from u to v avoiding e, and hence we have obtained the desired result.
Proof of 4: Paths of length 1 from u to v ∈ N 1 (v) yield transitive triangles with e as the base, and paths of length 2 from u to v ∈ {v} ∪ N 1 (v) yield 2-directed diamonds with e as one of the bases. By part 3, at least one of these structures exists, and hence we are done.
Proof of 5: | is the number of transitive triangles having base e, so we have proved the first half of part 5.
To prove the second half of this part, we consider the following cases: Case 1 : Suppose there exists a vertex u such that (u, u ), (u , v) ∈ E(M). By part 3, we know that u must be connected to at least |N 1 (v)| − 1 elements of N 1 (v) via a path of length 1 or 2 avoiding e. But we see that u is adjacent to at most |N 1 (u) − 2| vertices in N 1 (v). Subtracting, we see that u is connected via a path of length 2 avoiding e to at least ; each of which yields a 2-directed diamond of which e is the base, which is the desired result.
Case 2 : Suppose there is no such u . Then again applying part 3, it must be that there exists a path of length 1 or 2 avoiding e to each vertex in N 1 (v). But u is adjacent to at most |N 1 (u)| − 1 of these vertices, and as before we count that there is a path of length 2 avoiding e from u to at least |N 1 (v)| − (|N 1 (u)| − 1) = |N 1 (v)| − |N 1 (u)| + 1 vertices in |N 1 (v)|. Since each of these paths yield a 2-directed diamond with e as the base, we are done.
Proof of 6: In M, pick an arbitrary vertex u. Delete this vertex (and all edges incident with it) and label the resulting directed graph Z. Then in a similar manner to before, one of the vertices in N −1,M (u) must be satisfactory in Z by vertex minimality of M. Label this vertex t. Since |N 1,Z (t)| = |N 1,M (t)| − 1, t is satisfactory, and |N 2,Z (t)| ⊆ |N 2,M (t)| (note that in contrast to deleting an edge, deleting a vertex does not allow any vertices to add vertices to their second neighborhoods), we see that we must have |N 2,Z (t)| = |N 2,M (t)|. It is then necessary that A s,M (t) = 1. Since u was arbitrary, we have obtained the desired result.
Proof of 7: We apply the same technique as we used Theorem 3.1. We present a brief sketch of our proof: by part 5, each vertex in M has an in-neighbor having anti-satisfaction of exactly 1. If we begin at an arbitrary vertex and choose one of its in-neighbors having anti-satisfaction of exactly 1, do the same for the resulting vertex, and iterate this process, at some point we must arrive back at a vertex we have already visited, thus constructing a directed cycle of vertices having anti-satisfaction exactly 1.
Finally, we show that there is not a finite nonzero number of strongly-connected counterexamples to the conjecture. That is, either the conjecture is true, or there are an infinite number of (non-isomorphic) strongly-connected graphs that violate Conjecture 1.  Proof. Suppose that Seymour's Second Neighborhood Conjecture is false, and suppose that digraph D is any strongly-connected counterexample to Seymour's Second Neighborhood Conjecture. (By Part 1 of Theorem 4.1, such a D must exist.) Let H be any digraph satisfying the condition ∀v ∈ V (H), A s (v) ≥ 0; that is, all of H's vertices have nonnegative anti-satifaction. Note that any dicycle satisfies the relevant condition, and hence there exists a choice of H on any number n of vertices, n ≥ 3.
We now construct a graph D on |V (D)|·|V (H)| vertices such that D is a counterexample to Seymour's Second Neighborhood Conjecture, thus proving our theorem. We define our graph D as follows:   defines a directed path in D from (d 1 , h 1 ) to (d 2 , h 2 ). If d 1 = d 2 , let d 3 ∈ N 1,D (d 1 ); we know that (d 1 , h 1 ), (d 3 , h 2 ) are adjacent in D , and since d 2 = d 3 there is a path from (d 3 , h 2 ) to (d 2 , h 2 ) in D , the existence of a path from (d 1 , h 1 ) to (d 2 , h 2 ) follows.
By definition, we then have that D is a strongly-connected counterexample to Seymour's Second Neighborhood Conjecture.