Unnumbered (1.3): propagating-number inequality
ProvedQAlgorithms.Papers.Independent.Intake100.P88.propagatingNumber_composeLet and let be set partitions of the top and bottom rows of vertices. Write for stacking above , identifying their middle row, and retaining the induced partition of the outer rows. Let count blocks meeting both rows. Then
This is the structural bound underlying the propagating ideal.
import Definitions.Def_QAlgorithms_Papers_Independent_Intake100_P88
noncomputable section
namespace QAlgorithms.Papers.Independent.Intake100.P88
attribute [local instance] Classical.propDecidable
open scoped BigOperators Matrix
open QAlgorithms.Papers.Independent.Information100.P65 (hookLength)
open QAlgorithms.Papers.Independent.Renew46.P30 (TensorIndex)
universe u v w x y
/-- Propagating number under stacking, PDF p.4, equation (1.3). -/
theorem propagatingNumber_compose (k : ℕ) (_hk : 0 < k) (d e : PartitionDiagram k) :
propagatingNumber (diagramCompose d e) ≤ min (propagatingNumber d) (propagatingNumber e) := by sorry
end QAlgorithms.Papers.Independent.Intake100.P88
end
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
For every natural number and any equivalence relations on , define their composition by placing on layers and on layers , identifying their layer- vertices with equal indices, taking the equivalence relation generated by all these relations, and restricting it to the outer layers , viewed again as the false and true rows. For any diagram , let be the number of its equivalence classes containing at least one vertex from each row. Then , where denotes the composition just described. No pairing or planarity assumption is imposed on or .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.