Lemma 3, p. 1018 — a β-cycle of a subhypergraph G_{V′} gives a β-cycle of G of the same length
ProvedRunIntersect.Strict.lemma_3beta-acyclichypergraphp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1subhypergraph
Let be a hypergraph and . If the subhypergraph contains a β-cycle of length , then contains a β-cycle of length . In particular,
The lemma lets a short β-cycle found in an induced subhypergraph be transported back to ; it is used in the proof of Proposition 5 to show that the subhypergraph induced by a shortest β-cycle has a very rigid shape.
Preamble
import Mathlib import Definitions.Def_RunIntersect_Strict_Setting
Formal statement
namespace RunIntersect.Strict
/-- Lemma 3, p. 1018: a β-cycle of length `t` of the subhypergraph `G_W` (`W ⊆ V`) gives a β-cycle of
length `t` of `G`; in particular `G_W` is β-acyclic when `G` is. -/
theorem lemma_3 {α : Type*} [Fintype α] [DecidableEq α] (G : Hypergraph α) (W : Finset α)
(hW : W ⊆ G.V) :
(∀ (t : ℕ) (v : Fin t → α) (e : Fin t → Finset α), IsBetaCycle (subHg G W) t v e →
∃ (v' : Fin t → α) (e' : Fin t → Finset α), IsBetaCycle G t v' e') ∧
(IsBetaAcyclic G → IsBetaAcyclic (subHg G W)) := by sorry
end RunIntersect.Strict
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.