Per-face deletion bounds survive transport to simplex colours
ProvedWikipedia.SzemeredisTheorem.normalizedDeletionCost_orderedDeletionToSimplex_leadditive-combinatoricsgreen-tao-port-8822number-theory
Let be a nonempty finite vertex type and let be a deletion family on the ordered rank- facets of parts. If every ordered face has deletion density at most a real number , then the corresponding simplex-colour deletion family has normalized total deletion cost at most . The transport uses the canonical identification of a colour with its omitted-coordinate facet.
Preamble
/- Mechanically transplanted from https://github.com/plby/lean-proofs.git at 8822f7ddef30fadbd92e1c6ab4ed897af356af5e. Original scopes and proof bytes are oracle-derived. -/ import Definitions.Def_GreenTaoPort_Wikipedia_SzemeredisTheorem_ArithmeticProgression_Count import Definitions.Def_GreenTaoPort_Wikipedia_SzemeredisTheorem_Finite_Mean import Definitions.Def_GreenTaoPort_Wikipedia_SzemeredisTheorem_Hypergraph_APCorrespondence import Definitions.Def_GreenTaoPort_Wikipedia_SzemeredisTheorem_Hypergraph_APRemoval import Definitions.Def_GreenTaoPort_Wikipedia_SzemeredisTheorem_Hypergraph_ConditionalAverage import Definitions.Def_GreenTaoPort_Wikipedia_SzemeredisTheorem_Hypergraph_Energy import Definitions.Def_GreenTaoPort_Wikipedia_SzemeredisTheorem_Hypergraph_FacePartition import Definitions.Def_GreenTaoPort_Wikipedia_SzemeredisTheorem_Hypergraph_OrderedPattern import Definitions.Def_GreenTaoPort_Wikipedia_SzemeredisTheorem_Hypergraph_OrderedSimplexBridge import Definitions.Def_GreenTaoPort_Wikipedia_SzemeredisTheorem_Hypergraph_Removal import Definitions.Def_GreenTaoPort_Wikipedia_SzemeredisTheorem_Hypergraph_Simplex import Definitions.Def_GreenTaoPort_Wikipedia_SzemeredisTheorem_Hypergraph_Unweighted import Definitions.Def_GreenTaoPort_Wikipedia_SzemeredisTheorem_LinearForms_Basic import Definitions.Def_GreenTaoPort_Wikipedia_SzemeredisTheorem_Szemeredi_Weighted import Definitions.Def_GreenTaoPort_Wikipedia_SzemeredisTheorem_Transference_APCut import Definitions.Def_GreenTaoPort_Wikipedia_SzemeredisTheorem_Transference_CutDiscrepancy import Definitions.Def_GreenTaoPort_Wikipedia_SzemeredisTheorem_Transference_CutTransport import Mathlib.Algebra.BigOperators.Expect import Mathlib.Algebra.BigOperators.Fin import Mathlib.Algebra.Order.BigOperators.Expect import Mathlib.Algebra.Order.BigOperators.GroupWithZero.Finset import Mathlib.Data.Fin.Tuple.Basic import Mathlib.Data.Finset.Max import Mathlib.Data.Fintype.Card import Mathlib.Data.Int.Lemmas import Mathlib.Data.ZMod.Basic import Mathlib.Data.ZMod.Units import Mathlib.Order.Hom.PowersetCard import Mathlib.Order.Partition.Finpartition import Mathlib.RingTheory.Int.Basic import Mathlib.Tactic set_option autoImplicit true set_option relaxedAutoImplicit false set_option maxSynthPendingDepth 3 /-! # Equal-vertex bridge from ordered removal to simplex removal For `n + 1` equal vertex classes, the colours of a partite `n`-uniform simplex hypergraph are canonically the increasing `n`-faces of `Fin (n + 1)`: the colour `j` corresponds to the face which omits `j`. This file makes that identification explicit and transports occurrences, deletion covers, and normalized deletion cost. -/ open Wikipedia.SzemeredisTheorem open scoped BigOperators
Formal statement
theorem Wikipedia.SzemeredisTheorem.normalizedDeletionCost_orderedDeletionToSimplex_le
{G : Type*} [Fintype G] [DecidableEq G] [Nonempty G]
{n : ℕ}
(D : OrderedPattern.DeletionFamily
(G := G) (n + 1) n)
{ε : ℝ}
(hD :
∀ e, OrderedPattern.faceDeletionDensity D e ≤ ε) :
SimplexHypergraph.normalizedDeletionCost
(orderedDeletionToSimplex D) ≤ ε := by sorry
Source