Documentation

Mathlib.Combinatorics.Hall.Finite

Hall's Marriage Theorem for finite index types #

This module proves the basic form of Hall's theorem. In contrast to the theorem described in Combinatorics.Hall.Basic, this version requires that the indexed family t : ι → Finset α have ι be finite. The Combinatorics.Hall.Basic module applies a compactness argument to this version to remove the Finite constraint on ι.

The modules are split like this since the generalized statement depends on the topology and category theory libraries, but the finite case in this module has few dependencies.

A description of this formalization is in [Gusakov2021].

Main statements #

Tags #

Hall's Marriage Theorem, indexed families

theorem HallMarriageTheorem.hall_cond_of_erase {ι : Type u} {α : Type v} [DecidableEq α] {t : ιFinset α} [Fintype ι] {x : ι} (a : α) (ha : ∀ (s : Finset ι), s.Nonemptys Finset.univs.card < (Finset.biUnion s t).card) (s' : Finset {x' : ι | x' x}) :
s'.card (Finset.biUnion s' fun (x' : {x' : ι | x' x}) => Finset.erase (t x') a).card
theorem HallMarriageTheorem.hall_hard_inductive_step_A {ι : Type u} {α : Type v} [DecidableEq α] {t : ιFinset α} [Fintype ι] {n : } (hn : Fintype.card ι = n + 1) (ht : ∀ (s : Finset ι), s.card (Finset.biUnion s t).card) (ih : ∀ {ι' : Type u} [inst : Fintype ι'] (t' : ι'Finset α), Fintype.card ι' n(∀ (s' : Finset ι'), s'.card (Finset.biUnion s' t').card)∃ (f : ι'α), Function.Injective f ∀ (x : ι'), f x t' x) (ha : ∀ (s : Finset ι), s.Nonemptys Finset.univs.card < (Finset.biUnion s t).card) :
∃ (f : ια), Function.Injective f ∀ (x : ι), f x t x

First case of the inductive step: assuming that ∀ (s : Finset ι), s.Nonempty → s ≠ univ → s.card < (s.biUnion t).card and that the statement of Hall's Marriage Theorem is true for all ι' of cardinality ≤ n, then it is true for ι of cardinality n + 1.

theorem HallMarriageTheorem.hall_cond_of_restrict {α : Type v} [DecidableEq α] {ι : Type u} {t : ιFinset α} {s : Finset ι} (ht : ∀ (s : Finset ι), s.card (Finset.biUnion s t).card) (s' : Finset s) :
s'.card (Finset.biUnion s' fun (a' : s) => t a').card
theorem HallMarriageTheorem.hall_cond_of_compl {α : Type v} [DecidableEq α] {ι : Type u} {t : ιFinset α} {s : Finset ι} (hus : s.card = (Finset.biUnion s t).card) (ht : ∀ (s : Finset ι), s.card (Finset.biUnion s t).card) (s' : Finset (s)) :
s'.card (Finset.biUnion s' fun (x' : (s)) => t x' \ Finset.biUnion s t).card
theorem HallMarriageTheorem.hall_hard_inductive_step_B {ι : Type u} {α : Type v} [DecidableEq α] {t : ιFinset α} [Fintype ι] {n : } (hn : Fintype.card ι = n + 1) (ht : ∀ (s : Finset ι), s.card (Finset.biUnion s t).card) (ih : ∀ {ι' : Type u} [inst : Fintype ι'] (t' : ι'Finset α), Fintype.card ι' n(∀ (s' : Finset ι'), s'.card (Finset.biUnion s' t').card)∃ (f : ι'α), Function.Injective f ∀ (x : ι'), f x t' x) (s : Finset ι) (hs : s.Nonempty) (hns : s Finset.univ) (hus : s.card = (Finset.biUnion s t).card) :
∃ (f : ια), Function.Injective f ∀ (x : ι), f x t x

Second case of the inductive step: assuming that ∃ (s : Finset ι), s ≠ univ → s.card = (s.biUnion t).card and that the statement of Hall's Marriage Theorem is true for all ι' of cardinality ≤ n, then it is true for ι of cardinality n + 1.

theorem HallMarriageTheorem.hall_hard_inductive {ι : Type u} {α : Type v} [DecidableEq α] {t : ιFinset α} [Finite ι] (ht : ∀ (s : Finset ι), s.card (Finset.biUnion s t).card) :
∃ (f : ια), Function.Injective f ∀ (x : ι), f x t x

Here we combine the two inductive steps into a full strong induction proof, completing the proof the harder direction of Hall's Marriage Theorem.

theorem Finset.all_card_le_biUnion_card_iff_existsInjective' {ι : Type u_1} {α : Type u_2} [Finite ι] [DecidableEq α] (t : ιFinset α) :
(∀ (s : Finset ι), s.card (Finset.biUnion s t).card) ∃ (f : ια), Function.Injective f ∀ (x : ι), f x t x

This is the version of Hall's Marriage Theorem in terms of indexed families of finite sets t : ι → Finset α with ι finite. It states that there is a set of distinct representatives if and only if every union of k of the sets has at least k elements.

See Finset.all_card_le_biUnion_card_iff_exists_injective for a version where the Finite ι constraint is removed.