OctoInformBeta

Seymour's second-neighborhood conjecture

An oriented graph is a directed graph with no loops, no multiple arcs and no pair of opposite arcs. Write u→wu\to w when there is an arc from uu to ww. For a vertex vv, the set N1+(v)N_1^+(v) consists of the out-neighbors of vv, the vertices uu with v→uv\to u. The set N2+(v)N_2^+(v) consists of the vertices at directed distance exactly two from vv: the vertices ww outside {v}∪N1+(v)\{v\}\cup N_1^+(v) with v→u→wv\to u\to w for some vertex uu. A vertex vv is good when |N1+(v)|≤|N2+(v)||N_1^+(v)|\le|N_2^+(v)|. Seymour’s second neighborhood conjecture asserts that every nonempty finite oriented graph has a good vertex.

A tournament is an oriented graph with an arc between every two distinct vertices. The conjecture for tournaments was proved by Fisher. Fidler and Yuster extended the tournament case to tournaments missing a matching, a star or a clique. Ghazal corrected the proof of the star case. Chen, Shen and Yuster proved that every nonempty finite oriented graph has a vertex vv with |N2+(v)|≥γ|N1+(v)||N_2^+(v)|\ge\gamma\,|N_1^+(v)|, for a constant γ≈0.657298\gamma\approx 0.657298. Huang and Peng raised the constant to approximately 0.7155380.715538. For the binomial random graph with any fixed edge probability below 1/21/2, Espuny Díaz, Girão, Granet and Kronenberg proved that, with probability tending to one as the order tends to infinity, every orientation has a good vertex.

The preprint proves the conjecture, as its Theorem 1.1, with no connectivity or degree hypothesis.

The Lean library SecondNeighborhood proves Theorem 1.1 with no hypothesis beyond the preprint’s. Lean has checked every result of the Lean library, and the Lean library is therefore the reference. Each result on these pages is stated as the Lean library states it and is linked to the Lean declaration behind it. Where the preprint states a result differently, the preprint’s statement is given beside the Lean library’s. The preprint is a guide only: it gives the results their order and their names.

The Lean library: SecondNeighborhood

SecondNeighborhood is a Lean library: 19 items, in four groups. Each has a page written by OctoInform, listed below.

§1. Introduction 3 items
  1. Oriented graphs and exact out-neighborhoods Good vertices and the second-neighborhood conjecture for a digraph.
  2. Theorem 1.1 Every nonempty finite oriented graph has a good vertex.
  3. The image operator The second out-neighborhood as a difference of images.
§2. From a counterexample to a strict subset inequality 5 items
  1. Counterexamples, minimality and the subset conditions A counterexample is a digraph with no good vertex.
  2. Proposition 2.1 A counterexample yields an oriented graph with strict growth.
  3. Lemma 2.2 Minimal counterexamples have positive indegree and the subset deficit.
  4. The arc-deletion step Steps toward the subset deficit in an arc-minimal oriented counterexample.
  5. Lemma 2.3 Tournament blow-ups and the passage to strict growth.
§3. Pruning two families of pairs 7 items
  1. Conflicts, the sets Z and H, and covered points Conflicting pairs, covered points and what a pruning must achieve.
  2. Lemma 3.1 Two families of pairs can be pruned free of conflicts.
  3. Lemma 3.2 Kernel products vanish where a maximum-rank matrix may be nonzero.
  4. The augmented graph, the cover and the choice of matching Pruning two families of pairs through the augmented graph.
  5. Four maps with NL = AB Coefficients supported on the arcs make NLNL equal to ABAB.
  6. The simultaneous choice of coefficients Coefficients on the arcs maximizing several ranks at once.
  7. Kernel restriction and the matching bound Kernel vectors on conflicts and the bound |Z|+|H||Z|+|H| on matchings.
§4. The extremal contradiction 4 items
  1. Coordinate images, compatibility and the extremal objective Compatible pairs of families and the extremal objective.
  2. Proposition 4.1 Pruning excludes strict growth in oriented graphs of positive indegree.
  3. The steps of the proof of Proposition 4.1 The steps of the extremal argument for Proposition 4.1.
  4. Proof of Theorem 1.1 Every nonempty finite oriented graph has a good vertex.

No item matches.