Lemma 3, p. 1018 — a β-cycle of an induced subhypergraph lifts to G; subhypergraphs of β-acyclic hypergraphs are β-acyclic
ProvedRunIntersect.Tight.lemma_3beta-acyclichypergraphp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a hypergraph and . The subhypergraph induced by has node set and edges for with .
- If contains a β-cycle of length , then contains a β-cycle of length .
- In particular, if is β-acyclic, then is β-acyclic.
This is the hereditary property of β-acyclicity used throughout §3.3 and §5.3: it lets edge-induced pieces of a β-acyclic hypergraph inherit acyclicity.
Formalization Note A β-cycle of length is given by injective maps v : Fin t → α, e : Fin t → Finset α (0-based), see the Setting file.
Preamble
import Mathlib import Definitions.Def_RunIntersect_Tight_Setting
Formal statement
namespace RunIntersect.Tight
theorem lemma_3 {α : Type*} [Fintype α] [DecidableEq α] (G : Hypergraph α) (W : Finset α) (hW : W ⊆ G.V) :
(∀ t, (∃ v e, IsBetaCycle (subHg G W) t v e) → ∃ v e, IsBetaCycle G t v e) ∧
(IsBetaAcyclic G → IsBetaAcyclic (subHg G W)) := by sorry
end RunIntersect.Tight
Source
Del Pia and Khajavirad, The running intersection relaxation of the multilinear polytope, Math. Oper. Res. 46 (2021), p. 1018, Lemma 3
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.