Proposition 4.1 (extremal contradiction): no nonempty oriented graph with positive indegrees satisfies for every nonempty proper
OpenOAI.SeymourSecondNeighborhood.prop_4_1Let be a nonempty finite oriented graph on (a loopless asymmetric relation) in which every vertex has an in-neighbor, and let be its one-step image operator. Then is not a strict expander: it is impossible that
This is Proposition 4.1 of the manuscript and the heart of its argument. The proof there is an extremal argument on pairs of families : with the coordinate image operators and , call compatible if , and choose a compatible pair containing the diagonal that maximizes , where is the number of points of outside . Summing the strict expansion inequality over the columns of and the rows of (nonempty proper sets, by positive indegrees and compatibility) gives and ; the complements and then satisfy , contain the diagonal with its members conflict-free, and the set of their conflicts has at most points. The pruning lemma (Pruning.lemma_3_1) restores compatibility while deleting at most members, where counts the points left uncovered afterwards, so the pruned pair has objective , contradicting maximality. Together with Lemmas 2.2 and 2.3 this proposition implies Seymour's second-neighborhood conjecture (exists_goodVertex).
import Mathlib import Definitions.Def_SeymourSecondNeighborhood import Definitions.Def_SeymourSecondNeighborhood_Image open Finset
namespace OAI.SeymourSecondNeighborhood
variable {V : Type*} [Fintype V] [DecidableEq V]
theorem prop_4_1 [Nonempty V] (r : V → V → Prop) (hr : IsOriented r) (hin : PosIndeg r) :
¬ StrictExpander r := by
sorry
end OAI.SeymourSecondNeighborhood