Results on oriented graphs, matchings, generic ranks, pruning and weighted second neighborhoods, with their assumptions

The course proves the statements below; each link leads to the statement with its assumptions and its proof. The lessons are self-checked by the writing AI; independent mathematical review is not complete.

• Second out-neighborhoods as images — Lemma 1.1. In an oriented graph, v is not in F^2({v}), so N_2^+(v) = F^2({v}) minus F({v}).
• Closed strong components — Lemma 2.2. Every nonempty finite oriented graph has a strong component with no arc leaving it.
• Minimal counterexamples are strongly connected — Lemma 2.3. A minimal counterexample has at least two vertices, is strongly connected, and every vertex has an in-neighbor.
• Subset deficit (OpenAI, adapting Seacrest) — Proposition 3.3. In a minimal counterexample, |F^2(S) minus F(S)| < |F(S) minus S| for every nonempty proper vertex set S.
• Images in a transitive tournament — Lemma 1.3. For T in [m]: |T| - |f(T)| <= 1, f^2(T) in f(T), and |T| - 2|f(T)| + |f^2(T)| <= 1.
• The blow-up estimate — Proposition 2.2. In D[T_m], |U| - 2|F(U)| + |F^2(U)| <= m(|F^2(S) minus F(S)| - |F(S) minus S|) + |S minus F(S)| for U with support S.
• Strictly concave growth from the subset deficit (OpenAI) — Theorem 3.1. If D has positive in-degrees and the subset deficit and m > n, then D[T_m] has positive in-degrees and |U| + |F^2(U)| < 2|F(U)| for every nonempty proper U.
• Reduction (OpenAI) — Corollary 3.2. A counterexample to the second neighborhood conjecture yields a graph with positive in-degrees and strictly concave growth on every nonempty proper vertex set.
• Berge's augmenting paths — Lemma 1.1. A matching that is not maximum has an augmenting path.
• Koenig's theorem — Theorem 1.2. In a finite bipartite graph, the alternating-reachability set of a maximum matching gives a vertex cover of the same size containing no unmatched vertex.
• Rank and matchings — Lemma 2.1. The rank of a matrix supported on T is at most the largest size of a matching in T.
• Determinants of pattern matrices — Lemma 2.3. A square pattern matrix whose variable positions contain a perfect matching has a nonzero determinant polynomial; the same holds for block-diagonal combinations.
• Kernels at maximum rank — Lemma 2.4. If D has the largest rank among matrices supported on T, then x_j y_s = 0 for x in ker D, y in ker D^T and (s, j) in T.
• Pruning of two families of pairs (OpenAI) — Theorem 3.1. Two families of ordered pairs for any finite relation can be pruned to conflict-free subfamilies, keeping conflict-free members, deleting at most |H| plus the number of uncovered shared points.
• Columns and rows of compatible pairs — Lemma 1.3. With positive in-degrees, every column of P and row of Q of a compatible pair containing the diagonal is a nonempty proper vertex set.
• No strictly concave growth (OpenAI) — Theorem 2.1. No nonempty finite oriented graph with positive in-degrees has |U| + |F^2(U)| < 2|F(U)| for every nonempty proper U.
• Seymour's second neighborhood conjecture (OpenAI) — Theorem 3.1. Every nonempty finite oriented graph has a vertex v with |N_1^+(v)| <= |N_2^+(v)|.
• Arc-weighted form — Theorem 4.1. For nonnegative arc weights some vertex v has sum_s beta_v(s) >= sum_{u in N_1^+(v)} w(vu).
• Vertex-weighted form — Corollary 4.2. For nonnegative vertex weights some vertex v has eta(N_1^+(v)) <= eta(N_2^+(v)).
• A theorem of the alternative — Lemma 4.3. If no xi >= 0 has M^T xi < 0 in every coordinate, some probability vector eta has M eta >= 0.
• A balanced weighting — Corollary 4.4. Every nonempty finite oriented graph has a probability weighting with eta(N_1^+(v)) <= eta(N_2^+(v)) at every vertex.
• Graphs without directed triangles — Corollary 5.1. Without directed triangles some vertex has d^+(v) <= |Z(v)| and n - 1 >= 2 d^+(v) + d^-(v).
• Directed triangles from degrees n/3 — Corollary 5.2. Minimum in- and out-degree at least n/3 force a directed triangle.
• Regular graphs of girth four — Corollary 5.3. An r-regular oriented graph without directed triangles has at least 3r + 1 vertices; the bound is attained.

Reading order

Read the lessons in order; each uses the notation and results of the previous ones. The third lesson can be read independently.