An oriented graph is a directed graph with no loops, no multiple arcs and no pair of opposite arcs. Write when there is an arc from to . For a vertex , the set consists of the out-neighbors of , the vertices with . The set consists of the vertices at directed distance exactly two from : the vertices outside with for some vertex . A vertex is good when . 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 with , for a constant . Huang and Peng raised the constant to approximately . For the binomial random graph with any fixed edge probability below , 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.
SecondNeighborhood is a Lean library: 19 items, in four groups. Each has a page written by OctoInform, listed below.
No item matches.