matroid_sbo_reduction_pairs_of_two_indep
Let M be a finite strongly base-orderable matroid whose ground set is the union of two disjoint independent sets I and J. Then M has a reduction to a unit-capacity partition matroid with classes of size at most two: there is an involution p such that every subset T of the ground set containing no two distinct elements e, p e is independent in M.
Statement
theorem matroid_sbo_reduction_pairs_of_two_indep {α : Type*} (M : Matroid α) [M.Finite] (hM : matroid_strongly_base_orderable M) (I J : Set α) (hI : M.Indep I) (hJ : M.Indep J) (hIJ : Disjoint I J) (hE : I ∪ J = M.E) : ∃ p : α → α, Function.Involutive p ∧ ∀ T ⊆ M.E, (∀ e ∈ T, p e ∈ T → p e = e) → M.Indep T
- Formalizes
- arXiv:2610.07318 (A note on the list chromatic number of two matroids), Proposition 2.2. The classes are given as the orbits {e, p e} of an involution. The proof differs from the paper's: instead of applying strong base-orderability in the contraction by the common part of the two bases, the exchange bijection is made to fix that common part by successive transpositions, which keep the exchange property; disjointness of I and J is not used.
- Verified
- 08 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- matroid_strongly_base_orderableA matroid M is strongly base-orderable if for every two bases B₁, B₂ there is a bijection φ : B₁ → B₂ such that (B₁ \ X) ∪ φ(X) is a base…
- Used by 1
- matroid_sbo_list_colorable_two_of_colorable_twoIf M₁ and M₂ are strongly base-orderable matroids on a common finite ground set and each of them is 2-colorable (its ground set is the…
The proof, explained
The independent sets I and J are extended to bases B₁ and B₂ of the strongly base-orderable matroid M, which guarantees the existence of an exchange bijection between them. By an induction on the number of unfixed shared elements using transpositions, this exchange bijection can be chosen to fix every element in B₁ ∩ B₂. The candidate involution p is defined by swapping each element of B₁ \ B₂ with its image under the bijection, while fixing all other elements. Finally, any subset T containing no non-trivial orbit under p is shown to embed into an exchange base (B₁ \ X) ∪ φ(X), which proves that T is independent in M.
The exchange property for φ composed with the transposition of z = φ⁻¹(k) and k reduces to showing (B₁ \ X) ∪ φ((z k) '' X) = (B₁ \ Y) ∪ φ(Y) for a suitably modified set Y.
Fix a subset X ⊆ B₁, let k ∈ B₁ ∩ B₂ with φ(k) ≠ k, and let z = φ⁻¹(k) ∈ B₁. Since φ(k) ≠ k, we have z ≠ k. We record the standard action of the swap τ = (z k): it interchanges z and k and fixes every other element. Setting Y = X ∪ {k} if z ∈ X and Y = X \ {k} if z ∉ X, applying the exchange property of φ to Y reduces the exchange property of τ ∘ φ on X to establishing the equality of the two resulting base sets.
uses
Equiv.swap_apply_left,Equiv.swap_apply_right,Equiv.swap_apply_of_ne_of_ne,Subtype.extclassical intro X set z := φ.symm ⟨k, hk⟩ with hz have hφz : (φ z : α) = k := by simp [hz] have hzk : z ≠ k := fun h => hne (by rw [← h, hφz, h]) have hsz : Equiv.swap z k z = k := Equiv.swap_apply_left z k have hsk : Equiv.swap z k k = z := Equiv.swap_apply_right z k have hso : ∀ x, x ≠ z → x ≠ k → Equiv.swap z k x = x := fun x h1 h2 => Equiv.swap_apply_of_ne_of_ne h1 h2 have hkB : (k : α) ∈ B₁ := k.2 have hcoe : ∀ x : B₁, (x : α) = k → x = k := fun x h => Subtype.ext h set Y : Set B₁ := if z ∈ X then insert k X else X \ {k} with hY convert hφ Y using 1
The set equality (B₁ \ X) ∪ φ((z k) '' X) = (B₁ \ Y) ∪ φ(Y) holds when both z ∈ X and k ∈ X.
We unfold set membership into logical equivalences and perform a four-way case split on whether z and k belong to X. When both z ∈ X and k ∈ X, the definition of Y simplifies to Y = X. Furthermore, the swap τ = (z k) stabilizes X because it exchanges z and k and fixes the remaining elements. Since τ is an involution preserving X, the image under τ is X itself, and both sides coincide.
uses
Set.mem_union,Set.mem_sdiff,Set.mem_image,Equiv.trans_apply,if_pos,Set.insert_eq_of_mem,Equiv.swap_apply_selfext a simp only [Set.mem_union, Set.mem_sdiff, Set.mem_image, Equiv.trans_apply] by_cases hzX : z ∈ X <;> by_cases hkX : k ∈ X · have hYX : Y = X := by rw [hY, if_pos hzX, Set.insert_eq_of_mem hkX] rw [hYX] have hmem : ∀ x ∈ X, Equiv.swap z k x ∈ X := by intro x hx by_cases h1 : x = z · rw [h1, hsz]; exact hkX by_cases h2 : x = k · rw [h2, hsk]; exact hzX rw [hso x h1 h2]; exact hx constructor · rintro (h | ⟨x, hx, rfl⟩) · exact Or.inl h · exact Or.inr ⟨Equiv.swap z k x, hmem x hx, rfl⟩ · rintro (h | ⟨x, hx, rfl⟩) · exact Or.inl h · exact Or.inr ⟨Equiv.swap z k x, hmem x hx, by rw [Equiv.swap_apply_self]⟩
The set equality holds when z ∈ X and k ∉ X.
When z ∈ X and k ∉ X, the definition yields Y = X ∪ {k}. We verify inclusion in both directions: any element a ∈ B₁ \ X is either k (which equals φ(z) ∈ φ(Y)) or differs from k (placing it in B₁ \ Y); conversely, taking k out of B₁ \ X is compensated by φ(z) = k being in the image, while τ maps z ∈ X to k ∈ Y.
uses
if_pos,Set.mem_insert_of_mem,Set.mem_insert· have hYX : Y = insert k X := by rw [hY, if_pos hzX] rw [hYX] constructor · rintro (⟨haB, ha⟩ | ⟨x, hx, rfl⟩) · by_cases hak : a = k · exact Or.inr ⟨z, Set.mem_insert_of_mem _ hzX, by rw [hφz, hak]⟩ · refine Or.inl ⟨haB, ?_⟩ rintro ⟨x, hx, rfl⟩ rcases hx with rfl | hx · exact hak rfl · exact ha ⟨x, hx, rfl⟩ · refine Or.inr ⟨Equiv.swap z k x, ?_, rfl⟩ by_cases h1 : x = z · rw [h1, hsz]; exact Set.mem_insert _ _ have h2 : x ≠ k := fun h => hkX (h ▸ hx) rw [hso x h1 h2]; exact Set.mem_insert_of_mem _ hx · rintro (⟨haB, ha⟩ | ⟨x, hx, rfl⟩) · exact Or.inl ⟨haB, fun ⟨x, hx, hxa⟩ => ha ⟨x, Set.mem_insert_of_mem _ hx, hxa⟩⟩ · rcases hx with rfl | hx · exact Or.inr ⟨z, hzX, by rw [hsz]⟩ · by_cases h1 : x = z · subst h1 refine Or.inl ⟨by rw [hφz]; exact hkB, ?_⟩ rintro ⟨y, hy, hya⟩ rw [hφz] at hya exact hkX (hcoe y hya ▸ hy) · have h2 : x ≠ k := fun h => hkX (h ▸ hx) exact Or.inr ⟨x, hx, by rw [hso x h1 h2]⟩
The set equality holds when z ∉ X and k ∈ X.
When z ∉ X and k ∈ X, we have Y = X \ {k}. Symmetrically to the previous case, k ∈ X is mapped by τ to z, and φ(z) = k. Any element in B₁ \ X is already in B₁ \ Y, while in the image, τ(k) = z ensures that φ(τ(k)) = k ∈ B₁ \ Y, matching the two sides.
uses
if_neg· have hYX : Y = X \ {k} := by rw [hY, if_neg hzX] rw [hYX] constructor · rintro (⟨haB, ha⟩ | ⟨x, hx, rfl⟩) · exact Or.inl ⟨haB, fun ⟨x, hx, hxa⟩ => ha ⟨x, hx.1, hxa⟩⟩ · by_cases h2 : x = k · subst h2 refine Or.inl ⟨by rw [hsk, hφz]; exact hkB, ?_⟩ rintro ⟨y, hy, hya⟩ rw [hsk, hφz] at hya exact hy.2 (hcoe y hya) · have h1 : x ≠ z := fun h => hzX (h ▸ hx) exact Or.inr ⟨x, ⟨hx, h2⟩, by rw [hso x h1 h2]⟩ · rintro (⟨haB, ha⟩ | ⟨x, hx, rfl⟩) · by_cases hak : a = k · exact Or.inr ⟨k, hkX, by rw [hsk, hφz, hak]⟩ · refine Or.inl ⟨haB, ?_⟩ rintro ⟨x, hx, rfl⟩ exact ha ⟨x, ⟨hx, fun h => hak (by rw [h])⟩, rfl⟩ · have h1 : x ≠ z := fun h => hzX (h ▸ hx.1) exact Or.inr ⟨x, hx.1, by rw [hso x h1 hx.2]⟩
The set equality holds when neither z nor k belongs to X.
When z ∉ X and k ∉ X, we have Y = X. Because neither transposed element lies in X, the swap τ fixes every element of X pointwise. Therefore τ '' X = X, so φ(τ '' X) = φ(X) and both sides are identical.
uses
if_neg,Set.sdiff_singleton_eq_self· have hYX : Y = X := by rw [hY, if_neg hzX, Set.sdiff_singleton_eq_self hkX] rw [hYX] have hfix : ∀ x ∈ X, Equiv.swap z k x = x := fun x hx => hso x (fun h => hzX (h ▸ hx)) (fun h => hkX (h ▸ hx)) constructor · rintro (h | ⟨x, hx, rfl⟩) · exact Or.inl h · exact Or.inr ⟨x, hx, by rw [hfix x hx]⟩ · rintro (h | ⟨x, hx, rfl⟩) · exact Or.inl h · exact Or.inr ⟨x, hx, by rw [hfix x hx]⟩
To construct an exchange bijection fixing all common elements, it suffices to show by induction on n that any exchange bijection with at most n unfixed common elements can be modified to fix all of B₁ ∩ B₂.
Because B₁ is finite, the set of common elements not fixed by φ, {x ∈ B₁ ∩ B₂ | φ(x) ≠ x}, is finite. We formulate an induction principle on the cardinality n of this unfixed set; once proved for all n, the desired result follows by taking n to be the cardinality of the unfixed set for φ.
uses
le_rflhave : Finite B₁ := hfin.to_subtype suffices h : ∀ n : ℕ, ∀ φ : B₁ ≃ B₂, (∀ X : Set B₁, M.IsBase ((B₁ \ ((↑) '' X)) ∪ ((fun x => (φ x : α)) '' X))) → {x : B₁ | (x : α) ∈ B₂ ∧ (φ x : α) ≠ x}.ncard ≤ n → ∃ ψ : B₁ ≃ B₂, (∀ X : Set B₁, M.IsBase ((B₁ \ ((↑) '' X)) ∪ ((fun x => (ψ x : α)) '' X))) ∧ ∀ x : B₁, (x : α) ∈ B₂ → (ψ x : α) = x from h _ φ hφ le_rfl intro n
In the base case n = 0, any exchange bijection with at most 0 unfixed common elements already fixes every element of B₁ ∩ B₂.
If the unfixed set has cardinality at most 0, it must be empty. If there were any common element x with φ(x) ≠ x, the set would be nonempty and hence have strictly positive cardinality, contradicting the bound. Thus φ already fixes all common elements, so ψ = φ satisfies the requirements.
uses
Set.ncard_pos,Set.toFiniteinduction n with | zero => intro φ hφ hn refine ⟨φ, hφ, fun x hx => ?_⟩ by_contra h have : {x : B₁ | (x : α) ∈ B₂ ∧ (φ x : α) ≠ x}.Nonempty := ⟨x, hx, h⟩ rw [← Set.ncard_pos (Set.toFinite _)] at this omega
In the inductive step, swapping an unfixed common element with its preimage produces an exchange bijection with strictly fewer unfixed common elements, completing the induction.
If φ already fixes all common elements, we are done. Otherwise, let k ∈ B₁ ∩ B₂ be an unfixed element, and let z = φ⁻¹(k). By lemma sbo_exchange_swap, the modified bijection φ' = τ ∘ φ (with τ = (z k)) preserves the exchange property. Furthermore, φ'(k) = φ(z) = k, so k is now fixed. Any common element not fixed by φ' was already not fixed by φ and cannot be k, so the unfixed set for φ' is contained in that of φ minus {k}. Its cardinality is at most (n + 1) - 1 = n, so the induction hypothesis applies to φ'.
uses
sbo_exchange_swap,Equiv.trans_apply,Equiv.swap_apply_right,Set.ncard_le_ncard,Set.toFinite,Set.ncard_sdiff_singleton_of_mem| succ n ih => intro φ hφ hn by_cases hall : ∀ x : B₁, (x : α) ∈ B₂ → (φ x : α) = x · exact ⟨φ, hφ, hall⟩ push Not at hall obtain ⟨k, hk, hne⟩ := hall set z := φ.symm ⟨k, hk⟩ with hz have hφz : (φ z : α) = k := by simp [hz] have hzk : z ≠ k := fun h => hne (by rw [← h, hφz, h]) set φ' := (Equiv.swap z k).trans φ with hφ' apply ih φ' (sbo_exchange_swap M φ hφ k hk hne) have hsub : {x : B₁ | (x : α) ∈ B₂ ∧ (φ' x : α) ≠ x} ⊆ {x : B₁ | (x : α) ∈ B₂ ∧ (φ x : α) ≠ x} \ {k} := by rintro x ⟨hx2, hxne⟩ refine ⟨⟨hx2, ?_⟩, ?_⟩ · by_cases h1 : x = z · rw [h1, hφz]; exact fun h => hzk (Subtype.ext h.symm) · by_cases h2 : x = k · subst h2; exact hne · rwa [hφ', Equiv.trans_apply, Equiv.swap_apply_of_ne_of_ne h1 h2] at hxne · rintro rfl apply hxne rw [hφ', Equiv.trans_apply, Equiv.swap_apply_right, hφz] have hk' : k ∈ {x : B₁ | (x : α) ∈ B₂ ∧ (φ x : α) ≠ x} := ⟨hk, hne⟩ have := Set.ncard_le_ncard hsub (Set.toFinite _) rw [Set.ncard_sdiff_singleton_of_mem hk'] at this omegaExtend I and J to bases B₁ and B₂, obtain an exchange bijection φ fixing B₁ ∩ B₂, and define the candidate involution p.
We extend the independent sets I and J to bases B₁ and B₂ of M. By strong base orderability, there exists an exchange bijection between them, and by lemma sbo_exchange_fix_common, we may choose an exchange bijection φ : B₁ ≃ B₂ that fixes every element in B₁ ∩ B₂. We then define p : α → α by sending a ∈ B₁ to φ(a), sending a ∈ B₂ \ B₁ to φ⁻¹(a), and fixing all other elements.
uses
sbo_exchange_fix_commonclassical obtain ⟨B₁, hB₁, hIB⟩ := hI.exists_isBase_superset obtain ⟨B₂, hB₂, hJB⟩ := hJ.exists_isBase_superset obtain ⟨φ₀, hφ₀⟩ := hM B₁ B₂ hB₁ hB₂ obtain ⟨φ, hφ, hfix⟩ := sbo_exchange_fix_common M (M.ground_finite.subset hB₁.subset_ground) φ₀ hφ₀ set p : α → α := fun a => if h : a ∈ B₁ then (φ ⟨a, h⟩ : α) else if h2 : a ∈ B₂ then (φ.symm ⟨a, h2⟩ : α) else a with hp
The bijection φ maps every element of B₁ \ B₂ outside of B₁.
Let a ∈ B₁ \ B₂. If φ(a) were in B₁, then φ(a) would belong to B₁ ∩ B₂. Since φ fixes every element of B₁ ∩ B₂, we would have φ(φ(a)) = φ(a). By injectivity of φ, this implies φ(a) = a, which would place a in B₂, contradicting a ∉ B₂.
uses
Subtype.ext,congrArg-- an element of `B₁ \ B₂` is sent outside `B₁` have hout : ∀ (a : α) (h : a ∈ B₁), a ∉ B₂ → (φ ⟨a, h⟩ : α) ∉ B₁ := by intro a h ha hb have h2 : (φ ⟨a, h⟩ : α) ∈ B₂ := (φ ⟨a, h⟩).2 have := hfix ⟨_, hb⟩ h2 have hinj : φ ⟨(φ ⟨a, h⟩ : α), hb⟩ = φ ⟨a, h⟩ := Subtype.ext this have := φ.injective hinj have h3 : (φ ⟨a, h⟩ : α) = a := congrArg Subtype.val this exact ha (h3 ▸ h2)
The map p is an involution on α.
We analyze the position of an arbitrary element a with respect to B₁ and B₂. If a ∈ B₁ ∩ B₂, then φ(a) = a, so p(a) = a and p(p(a)) = a. If a ∈ B₁ \ B₂, then p(a) = φ(a) ∈ B₂ \ B₁ by the previous step, so p(p(a)) = φ⁻¹(φ(a)) = a. If a ∈ B₂ \ B₁, then p(a) = φ⁻¹(a) ∈ B₁, so p(p(a)) = φ(φ⁻¹(a)) = a. Finally, if a ∉ B₁ ∪ B₂, p fixes a, so p(p(a)) = a.
uses
dif_pos,dif_negrefine ⟨p, ?_, ?_⟩ · intro a by_cases h : a ∈ B₁ · by_cases h2 : a ∈ B₂ · have hf := hfix ⟨a, h⟩ h2 simp only [hp, dif_pos h] simp only [hf, dif_pos h] · have hb := hout a h h2 have hb2 : (φ ⟨a, h⟩ : α) ∈ B₂ := (φ ⟨a, h⟩).2 simp only [hp, dif_pos h, dif_neg hb, dif_pos hb2] simp · by_cases h2 : a ∈ B₂ · have hc : (φ.symm ⟨a, h2⟩ : α) ∈ B₁ := (φ.symm ⟨a, h2⟩).2 simp only [hp, dif_neg h, dif_pos h2, dif_pos hc] simp · simp only [hp, dif_neg h, dif_neg h2]
For any T ⊆ M.E containing no distinct pair {e, p(e)}, showing independence of T reduces to showing T ⊆ B' = (B₁ \ X) ∪ φ(X) for X = {x ∈ B₁ | φ(x) ∈ T ∧ x ∉ B₂}, and every t ∈ T ∩ B₁ belongs to B₁ \ X.
By the exchange property of φ, the set B' = (B₁ \ X) ∪ φ(X) is a base of M, hence independent. Since any subset of an independent set is independent, it suffices to show T ⊆ B'. For t ∈ T ∩ B₁: if t were in X, then φ(t) ∈ T and t ∉ B₂. Since t ∈ B₁ \ B₂, p(t) = φ(t) ∈ T. The condition on T then forces p(t) = t, meaning φ(t) = t ∈ B₂, which contradicts t ∉ B₂. Thus t ∉ X, so t ∈ B₁ \ X ⊆ B'.
· intro T hT hTp set X : Set B₁ := {x | (φ x : α) ∈ T ∧ (x : α) ∉ B₂} with hX refine (hφ X).indep.subset ?_ intro t ht by_cases htB : t ∈ B₁ · refine Or.inl ⟨htB, ?_⟩ rintro ⟨x, ⟨hxT, hxB⟩, rfl⟩ have hpx : p x = (φ x : α) := by simp [hp, x.2] have := hTp x ht (hpx ▸ hxT) rw [hpx] at this exact hxB (this ▸ (φ x).2) · have htE : t ∈ I ∪ J := hE ▸ hT ht
Every element t ∈ T \ B₁ belongs to φ(X) ⊆ B', establishing T ⊆ B' and completing the proof of independence.
Since t ∈ T ⊆ M.E = I ∪ J and t ∉ B₁ (which contains I), t must belong to J ⊆ B₂. Let x = φ⁻¹(t) ∈ B₁. If x were in B₂, then x ∈ B₁ ∩ B₂, so φ(x) = x, which would imply t = x ∈ B₁, a contradiction. Thus x ∉ B₂, and since φ(x) = t ∈ T, we have x ∈ X. Consequently, t = φ(x) ∈ φ(X) ⊆ B', which shows T ⊆ B' and proves that T is independent.
have htB2 : t ∈ B₂ := by rcases htE with h | h · exact absurd (hIB h) htB · exact hJB h set x := φ.symm ⟨t, htB2⟩ with hx have hφx : (φ x : α) = t := by simp [hx] have hxB : (x : α) ∉ B₂ := by intro h have := hfix x h rw [hφx] at this exact htB (this ▸ x.2) exact Or.inr ⟨x, ⟨hφx ▸ ht, hxB⟩, hφx⟩
congrArg- The equality f(a₁) = f(a₂) follows from a₁ = a₂.
dif_neg- A dependent if-then-else evaluates to the else-branch when the condition is false.
dif_pos- A dependent if-then-else evaluates to the then-branch when the condition is true.
Equiv.swap_apply_left- Swapping a and b maps a to b.
Equiv.swap_apply_of_ne_of_ne- Swapping a and b fixes any element distinct from both a and b.
Equiv.swap_apply_right- Swapping a and b maps b to a.
Equiv.swap_apply_self- Applying the swap of two elements twice to any element returns the original element.
Equiv.trans_apply- The composition (f.trans g)(a) is equal to g(f(a)).
if_neg- An if-then-else evaluates to the else-branch when the condition is false.
if_pos- An if-then-else evaluates to the then-branch when the condition is true.
le_rfl- The inequality relation on a preorder is reflexive: a ≤ a.
sbo_exchange_fix_common- In a matroid, an exchange bijection between two finite bases can be chosen to fix every element common to both bases.
sbo_exchange_swap- Composing an exchange bijection with the transposition of an unfixed common element and its preimage preserves the exchange property.
Set.insert_eq_of_mem- Inserting an element into a set that already contains it leaves the set unchanged.
Set.mem_image- An element y is in the image f '' s if and only if y = f(x) for some x ∈ s.
Set.mem_insert- The element x belongs to the set insert x s.
Set.mem_insert_of_mem- If x ∈ s, then x belongs to insert y s.
Set.mem_sdiff- An element belongs to s \ t if and only if it belongs to s and does not belong to t.
Set.mem_union- An element belongs to s ∪ t if and only if it belongs to s or to t.
Set.ncard_le_ncard- A subset of a finite set has cardinality at most that of the ambient set.
Set.ncard_pos- A finite set has strictly positive cardinality if and only if it is nonempty.
Set.ncard_sdiff_singleton_of_mem- Removing an element from a set reduces its cardinality by 1.
Set.sdiff_singleton_eq_self- Removing an element from a set that does not contain it leaves the set unchanged.
Set.toFinite- A set whose subtype is finite is finite as a set.
Subtype.ext- Two elements of a subtype are equal if their underlying values are equal.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- One swap: composing an exchange bijection `φ : B₁ ≃ B₂` with the transposition of`z = φ⁻¹(k)` and `k` (for `k ∈ B₁ ∩ B₂`) keeps the exchange property. -/theorem sbo_exchange_swap {α : Type*} [DecidableEq α] (M : Matroid α) {B₁ B₂ : Set α} (φ : B₁ ≃ B₂) (hφ : ∀ X : Set B₁, M.IsBase ((B₁ \ ((↑) '' X)) ∪ ((fun x => (φ x : α)) '' X))) (k : B₁) (hk : (k : α) ∈ B₂) (hne : (φ k : α) ≠ k) : ∀ X : Set B₁, M.IsBase ((B₁ \ ((↑) '' X)) ∪ ((fun x => (((Equiv.swap (φ.symm ⟨k, hk⟩) k).trans φ) x : α)) '' X)) := by classical intro X set z := φ.symm ⟨k, hk⟩ with hz have hφz : (φ z : α) = k := by simp [hz] have hzk : z ≠ k := fun h => hne (by rw [← h, hφz, h]) have hsz : Equiv.swap z k z = k := Equiv.swap_apply_left z k have hsk : Equiv.swap z k k = z := Equiv.swap_apply_right z k have hso : ∀ x, x ≠ z → x ≠ k → Equiv.swap z k x = x := fun x h1 h2 => Equiv.swap_apply_of_ne_of_ne h1 h2 have hkB : (k : α) ∈ B₁ := k.2 have hcoe : ∀ x : B₁, (x : α) = k → x = k := fun x h => Subtype.ext h set Y : Set B₁ := if z ∈ X then insert k X else X \ {k} with hY convert hφ Y using 1 ext a simp only [Set.mem_union, Set.mem_sdiff, Set.mem_image, Equiv.trans_apply] by_cases hzX : z ∈ X <;> by_cases hkX : k ∈ X · have hYX : Y = X := by rw [hY, if_pos hzX, Set.insert_eq_of_mem hkX] rw [hYX] have hmem : ∀ x ∈ X, Equiv.swap z k x ∈ X := by intro x hx by_cases h1 : x = z · rw [h1, hsz]; exact hkX by_cases h2 : x = k · rw [h2, hsk]; exact hzX rw [hso x h1 h2]; exact hx constructor · rintro (h | ⟨x, hx, rfl⟩) · exact Or.inl h · exact Or.inr ⟨Equiv.swap z k x, hmem x hx, rfl⟩ · rintro (h | ⟨x, hx, rfl⟩) · exact Or.inl h · exact Or.inr ⟨Equiv.swap z k x, hmem x hx, by rw [Equiv.swap_apply_self]⟩ · have hYX : Y = insert k X := by rw [hY, if_pos hzX] rw [hYX] constructor · rintro (⟨haB, ha⟩ | ⟨x, hx, rfl⟩) · by_cases hak : a = k · exact Or.inr ⟨z, Set.mem_insert_of_mem _ hzX, by rw [hφz, hak]⟩ · refine Or.inl ⟨haB, ?_⟩ rintro ⟨x, hx, rfl⟩ rcases hx with rfl | hx · exact hak rfl · exact ha ⟨x, hx, rfl⟩ · refine Or.inr ⟨Equiv.swap z k x, ?_, rfl⟩ by_cases h1 : x = z · rw [h1, hsz]; exact Set.mem_insert _ _ have h2 : x ≠ k := fun h => hkX (h ▸ hx) rw [hso x h1 h2]; exact Set.mem_insert_of_mem _ hx · rintro (⟨haB, ha⟩ | ⟨x, hx, rfl⟩) · exact Or.inl ⟨haB, fun ⟨x, hx, hxa⟩ => ha ⟨x, Set.mem_insert_of_mem _ hx, hxa⟩⟩ · rcases hx with rfl | hx · exact Or.inr ⟨z, hzX, by rw [hsz]⟩ · by_cases h1 : x = z · subst h1 refine Or.inl ⟨by rw [hφz]; exact hkB, ?_⟩ rintro ⟨y, hy, hya⟩ rw [hφz] at hya exact hkX (hcoe y hya ▸ hy) · have h2 : x ≠ k := fun h => hkX (h ▸ hx) exact Or.inr ⟨x, hx, by rw [hso x h1 h2]⟩ · have hYX : Y = X \ {k} := by rw [hY, if_neg hzX] rw [hYX] constructor · rintro (⟨haB, ha⟩ | ⟨x, hx, rfl⟩) · exact Or.inl ⟨haB, fun ⟨x, hx, hxa⟩ => ha ⟨x, hx.1, hxa⟩⟩ · by_cases h2 : x = k · subst h2 refine Or.inl ⟨by rw [hsk, hφz]; exact hkB, ?_⟩ rintro ⟨y, hy, hya⟩ rw [hsk, hφz] at hya exact hy.2 (hcoe y hya) · have h1 : x ≠ z := fun h => hzX (h ▸ hx) exact Or.inr ⟨x, ⟨hx, h2⟩, by rw [hso x h1 h2]⟩ · rintro (⟨haB, ha⟩ | ⟨x, hx, rfl⟩) · by_cases hak : a = k · exact Or.inr ⟨k, hkX, by rw [hsk, hφz, hak]⟩ · refine Or.inl ⟨haB, ?_⟩ rintro ⟨x, hx, rfl⟩ exact ha ⟨x, ⟨hx, fun h => hak (by rw [h])⟩, rfl⟩ · have h1 : x ≠ z := fun h => hzX (h ▸ hx.1) exact Or.inr ⟨x, hx.1, by rw [hso x h1 hx.2]⟩ · have hYX : Y = X := by rw [hY, if_neg hzX, Set.sdiff_singleton_eq_self hkX] rw [hYX] have hfix : ∀ x ∈ X, Equiv.swap z k x = x := fun x hx => hso x (fun h => hzX (h ▸ hx)) (fun h => hkX (h ▸ hx)) constructor · rintro (h | ⟨x, hx, rfl⟩) · exact Or.inl h · exact Or.inr ⟨x, hx, by rw [hfix x hx]⟩ · rintro (h | ⟨x, hx, rfl⟩) · exact Or.inl h · exact Or.inr ⟨x, hx, by rw [hfix x hx]⟩/-- In a matroid, an exchange bijection between two finite bases can be chosen to fix everyelement the two bases share. -/theorem sbo_exchange_fix_common {α : Type*} [DecidableEq α] (M : Matroid α) {B₁ B₂ : Set α} (hfin : B₁.Finite) (φ : B₁ ≃ B₂) (hφ : ∀ X : Set B₁, M.IsBase ((B₁ \ ((↑) '' X)) ∪ ((fun x => (φ x : α)) '' X))) : ∃ ψ : B₁ ≃ B₂, (∀ X : Set B₁, M.IsBase ((B₁ \ ((↑) '' X)) ∪ ((fun x => (ψ x : α)) '' X))) ∧ ∀ x : B₁, (x : α) ∈ B₂ → (ψ x : α) = x := by have : Finite B₁ := hfin.to_subtype suffices h : ∀ n : ℕ, ∀ φ : B₁ ≃ B₂, (∀ X : Set B₁, M.IsBase ((B₁ \ ((↑) '' X)) ∪ ((fun x => (φ x : α)) '' X))) → {x : B₁ | (x : α) ∈ B₂ ∧ (φ x : α) ≠ x}.ncard ≤ n → ∃ ψ : B₁ ≃ B₂, (∀ X : Set B₁, M.IsBase ((B₁ \ ((↑) '' X)) ∪ ((fun x => (ψ x : α)) '' X))) ∧ ∀ x : B₁, (x : α) ∈ B₂ → (ψ x : α) = x from h _ φ hφ le_rfl intro n induction n with | zero => intro φ hφ hn refine ⟨φ, hφ, fun x hx => ?_⟩ by_contra h have : {x : B₁ | (x : α) ∈ B₂ ∧ (φ x : α) ≠ x}.Nonempty := ⟨x, hx, h⟩ rw [← Set.ncard_pos (Set.toFinite _)] at this omega | succ n ih => intro φ hφ hn by_cases hall : ∀ x : B₁, (x : α) ∈ B₂ → (φ x : α) = x · exact ⟨φ, hφ, hall⟩ push Not at hall obtain ⟨k, hk, hne⟩ := hall set z := φ.symm ⟨k, hk⟩ with hz have hφz : (φ z : α) = k := by simp [hz] have hzk : z ≠ k := fun h => hne (by rw [← h, hφz, h]) set φ' := (Equiv.swap z k).trans φ with hφ' apply ih φ' (sbo_exchange_swap M φ hφ k hk hne) have hsub : {x : B₁ | (x : α) ∈ B₂ ∧ (φ' x : α) ≠ x} ⊆ {x : B₁ | (x : α) ∈ B₂ ∧ (φ x : α) ≠ x} \ {k} := by rintro x ⟨hx2, hxne⟩ refine ⟨⟨hx2, ?_⟩, ?_⟩ · by_cases h1 : x = z · rw [h1, hφz]; exact fun h => hzk (Subtype.ext h.symm) · by_cases h2 : x = k · subst h2; exact hne · rwa [hφ', Equiv.trans_apply, Equiv.swap_apply_of_ne_of_ne h1 h2] at hxne · rintro rfl apply hxne rw [hφ', Equiv.trans_apply, Equiv.swap_apply_right, hφz] have hk' : k ∈ {x : B₁ | (x : α) ∈ B₂ ∧ (φ x : α) ≠ x} := ⟨hk, hne⟩ have := Set.ncard_le_ncard hsub (Set.toFinite _) rw [Set.ncard_sdiff_singleton_of_mem hk'] at this omegatheorem matroid_sbo_reduction_pairs_of_two_indep {α : Type*} (M : Matroid α) [M.Finite] (hM : matroid_strongly_base_orderable M) (I J : Set α) (hI : M.Indep I) (hJ : M.Indep J) (hIJ : Disjoint I J) (hE : I ∪ J = M.E) : ∃ p : α → α, Function.Involutive p ∧ ∀ T ⊆ M.E, (∀ e ∈ T, p e ∈ T → p e = e) → M.Indep T := by classical obtain ⟨B₁, hB₁, hIB⟩ := hI.exists_isBase_superset obtain ⟨B₂, hB₂, hJB⟩ := hJ.exists_isBase_superset obtain ⟨φ₀, hφ₀⟩ := hM B₁ B₂ hB₁ hB₂ obtain ⟨φ, hφ, hfix⟩ := sbo_exchange_fix_common M (M.ground_finite.subset hB₁.subset_ground) φ₀ hφ₀ set p : α → α := fun a => if h : a ∈ B₁ then (φ ⟨a, h⟩ : α) else if h2 : a ∈ B₂ then (φ.symm ⟨a, h2⟩ : α) else a with hp -- an element of `B₁ \ B₂` is sent outside `B₁` have hout : ∀ (a : α) (h : a ∈ B₁), a ∉ B₂ → (φ ⟨a, h⟩ : α) ∉ B₁ := by intro a h ha hb have h2 : (φ ⟨a, h⟩ : α) ∈ B₂ := (φ ⟨a, h⟩).2 have := hfix ⟨_, hb⟩ h2 have hinj : φ ⟨(φ ⟨a, h⟩ : α), hb⟩ = φ ⟨a, h⟩ := Subtype.ext this have := φ.injective hinj have h3 : (φ ⟨a, h⟩ : α) = a := congrArg Subtype.val this exact ha (h3 ▸ h2) refine ⟨p, ?_, ?_⟩ · intro a by_cases h : a ∈ B₁ · by_cases h2 : a ∈ B₂ · have hf := hfix ⟨a, h⟩ h2 simp only [hp, dif_pos h] simp only [hf, dif_pos h] · have hb := hout a h h2 have hb2 : (φ ⟨a, h⟩ : α) ∈ B₂ := (φ ⟨a, h⟩).2 simp only [hp, dif_pos h, dif_neg hb, dif_pos hb2] simp · by_cases h2 : a ∈ B₂ · have hc : (φ.symm ⟨a, h2⟩ : α) ∈ B₁ := (φ.symm ⟨a, h2⟩).2 simp only [hp, dif_neg h, dif_pos h2, dif_pos hc] simp · simp only [hp, dif_neg h, dif_neg h2] · intro T hT hTp set X : Set B₁ := {x | (φ x : α) ∈ T ∧ (x : α) ∉ B₂} with hX refine (hφ X).indep.subset ?_ intro t ht by_cases htB : t ∈ B₁ · refine Or.inl ⟨htB, ?_⟩ rintro ⟨x, ⟨hxT, hxB⟩, rfl⟩ have hpx : p x = (φ x : α) := by simp [hp, x.2] have := hTp x ht (hpx ▸ hxT) rw [hpx] at this exact hxB (this ▸ (φ x).2) · have htE : t ∈ I ∪ J := hE ▸ hT ht have htB2 : t ∈ B₂ := by rcases htE with h | h · exact absurd (hIB h) htB · exact hJB h set x := φ.symm ⟨t, htB2⟩ with hx have hφx : (φ x : α) = t := by simp [hx] have hxB : (x : α) ∉ B₂ := by intro h have := hfix x h rw [hφx] at this exact htB (this ▸ x.2) exact Or.inr ⟨x, ⟨hφx ▸ ht, hxB⟩, hφx⟩