Splitting a finite set into parts of prescribed sizes
ProvedFinsetParts.exists_parts_card_eqcombinatoricsfinsets
Let be a finite set and let with . Then there are subsets with for all such that every element of lies in exactly one . That is, .
Preamble
import Mathlib
Formal statement
namespace FinsetParts
/-- Splitting a finite set into parts of prescribed sizes: if `b₁ + ⋯ + bₙ = |X|`, then `X` is the disjoint union of subsets `Y₁, …, Yₙ` with `|Yᵢ| = bᵢ`. -/
theorem exists_parts_card_eq {α : Type*} [DecidableEq α] {n : ℕ} (X : Finset α)
(b : Fin n → ℕ) (h : ∑ i, b i = X.card) :
∃ Y : Fin n → Finset α, (∀ i, Y i ⊆ X) ∧ (∀ i, (Y i).card = b i) ∧
∀ x ∈ X, ∃! i, x ∈ Y i := by sorry
end FinsetParts
Source
Standard combinatorics; used in J. Brakensiek, V. Guruswami, Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy, arXiv:1704.01937v2, proof of Lemma 4.10, pp. 22–23 (partitions S = S_1 ∪ … ∪ S_n)