Lemma 2.3 (transitive-tournament blow-up): with turns the subset deficit into strict expansion for every nonempty proper
ProvedOAI.SeymourSecondNeighborhood.lemma_2_3Let be an oriented graph on a finite vertex set with , in which every vertex has an in-neighbor and which satisfies the subset deficit for every nonempty proper . Let and let be the graph on obtained by replacing each vertex by a transitive tournament on labels (arcs from smaller to larger labels) and, for every arc of , putting all arcs from the block at to the block at (blowup r m). Then is an oriented graph, every vertex of has an in-neighbor, and
(StrictExpander), where is the one-step image operator of . This is Lemma 2.3 of the manuscript. In the proof, for a nonempty proper with label sets in the blocks and support , one has and , where is the image operator of the transitive tournament, which satisfies ; summing gives when , and when . The same product construction appears in Brantner, Brockman, Kay and Snively, Involve 2 (2009), Theorem 4.3.
import Mathlib import Definitions.Def_SeymourSecondNeighborhood import Definitions.Def_SeymourSecondNeighborhood_Image open Finset
namespace OAI.SeymourSecondNeighborhood
variable {V : Type*} [Fintype V] [DecidableEq V]
theorem lemma_2_3 (r : V → V → Prop) (hr : IsOriented r) (hin : PosIndeg r)
(hdef : SubsetDeficit r) (m : ℕ) (hm : Fintype.card V < m) :
IsOriented (blowup r m) ∧ PosIndeg (blowup r m) ∧ StrictExpander (blowup r m) := by
sorry
end OAI.SeymourSecondNeighborhood