combinatorics.simple_graph.matching | Mathlib porting status

Changes since the initial port

The following section lists changes to this file in mathlib3 and mathlib4 that occured after the initial port. Most recent changes are shown first. Hovering over a commit will show all commits associated with the same mathlib3 commit.

Changes in mathlib3

138448ae

(last sync)

Changes in mathlib3port

mathlib3

mathlib3port

31ca6f9c

bump to nightly-2024-03-17-08

mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83

22f01ce4

Diff

@@ -124,7 +124,7 @@ theorem isMatching_iff_forall_degree {M : Subgraph G} [∀ v : V, Fintype (M.nei
 theorem IsMatching.even_card {M : Subgraph G} [Fintype M.verts] (h : M.IsMatching) :
     Even M.verts.toFinset.card := by
   classical
-  rw [is_matching_iff_forall_degree] at h 
+  rw [is_matching_iff_forall_degree] at h
   use M.coe.edge_finset.card
   rw [← two_mul, ← M.coe.sum_degrees_eq_twice_card_edges]
   simp [h, Finset.card_univ]

31ca6f9c

bump to nightly-2024-02-01-06

mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83

5433bded

Diff

@@ -122,7 +122,12 @@ theorem isMatching_iff_forall_degree {M : Subgraph G} [∀ v : V, Fintype (M.nei
 
 #print SimpleGraph.Subgraph.IsMatching.even_card /-
 theorem IsMatching.even_card {M : Subgraph G} [Fintype M.verts] (h : M.IsMatching) :
-    Even M.verts.toFinset.card := by classical
+    Even M.verts.toFinset.card := by
+  classical
+  rw [is_matching_iff_forall_degree] at h 
+  use M.coe.edge_finset.card
+  rw [← two_mul, ← M.coe.sum_degrees_eq_twice_card_edges]
+  simp [h, Finset.card_univ]
 #align simple_graph.subgraph.is_matching.even_card SimpleGraph.Subgraph.IsMatching.even_card
 -/
 
@@ -146,7 +151,7 @@ theorem isPerfectMatching_iff_forall_degree {M : Subgraph G} [∀ v, Fintype (M.
 
 #print SimpleGraph.Subgraph.IsPerfectMatching.even_card /-
 theorem IsPerfectMatching.even_card {M : Subgraph G} [Fintype V] (h : M.IsPerfectMatching) :
-    Even (Fintype.card V) := by classical
+    Even (Fintype.card V) := by classical simpa [h.2.card_verts] using is_matching.even_card h.1
 #align simple_graph.subgraph.is_perfect_matching.even_card SimpleGraph.Subgraph.IsPerfectMatching.even_card
 -/

31ca6f9c

bump to nightly-2024-01-31-06

mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83

61100fe9

Diff

@@ -122,12 +122,7 @@ theorem isMatching_iff_forall_degree {M : Subgraph G} [∀ v : V, Fintype (M.nei
 
 #print SimpleGraph.Subgraph.IsMatching.even_card /-
 theorem IsMatching.even_card {M : Subgraph G} [Fintype M.verts] (h : M.IsMatching) :
-    Even M.verts.toFinset.card := by
-  classical
-  rw [is_matching_iff_forall_degree] at h 
-  use M.coe.edge_finset.card
-  rw [← two_mul, ← M.coe.sum_degrees_eq_twice_card_edges]
-  simp [h, Finset.card_univ]
+    Even M.verts.toFinset.card := by classical
 #align simple_graph.subgraph.is_matching.even_card SimpleGraph.Subgraph.IsMatching.even_card
 -/
 
@@ -151,7 +146,7 @@ theorem isPerfectMatching_iff_forall_degree {M : Subgraph G} [∀ v, Fintype (M.
 
 #print SimpleGraph.Subgraph.IsPerfectMatching.even_card /-
 theorem IsPerfectMatching.even_card {M : Subgraph G} [Fintype V] (h : M.IsPerfectMatching) :
-    Even (Fintype.card V) := by classical simpa [h.2.card_verts] using is_matching.even_card h.1
+    Even (Fintype.card V) := by classical
 #align simple_graph.subgraph.is_perfect_matching.even_card SimpleGraph.Subgraph.IsPerfectMatching.even_card
 -/

31ca6f9c

bump to nightly-2023-09-24-06

mathlib commit https://github.com/leanprover-community/mathlib/commit/ce64cd319bb6b3e82f31c2d38e79080d377be451

5655435f

Diff

@@ -3,8 +3,8 @@ Copyright (c) 2020 Alena Gusakov. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Alena Gusakov, Arthur Paulino, Kyle Miller
 -/
-import Mathbin.Combinatorics.SimpleGraph.DegreeSum
-import Mathbin.Combinatorics.SimpleGraph.Subgraph
+import Combinatorics.SimpleGraph.DegreeSum
+import Combinatorics.SimpleGraph.Subgraph
 
 #align_import combinatorics.simple_graph.matching from "leanprover-community/mathlib"@"31ca6f9cf5f90a6206092cd7f84b359dcb6d52e0"

31ca6f9c

bump to nightly-2023-07-20-09

mathlib commit https://github.com/leanprover-community/mathlib/commit/8ea5598db6caeddde6cb734aa179cc2408dbd345

9c56d0dd

Diff

@@ -2,15 +2,12 @@
 Copyright (c) 2020 Alena Gusakov. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Alena Gusakov, Arthur Paulino, Kyle Miller
-
-! This file was ported from Lean 3 source module combinatorics.simple_graph.matching
-! leanprover-community/mathlib commit 31ca6f9cf5f90a6206092cd7f84b359dcb6d52e0
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathbin.Combinatorics.SimpleGraph.DegreeSum
 import Mathbin.Combinatorics.SimpleGraph.Subgraph
 
+#align_import combinatorics.simple_graph.matching from "leanprover-community/mathlib"@"31ca6f9cf5f90a6206092cd7f84b359dcb6d52e0"
+
 /-!
 # Matchings

31ca6f9c

bump to nightly-2023-06-04-18

mathlib commit https://github.com/leanprover-community/mathlib/commit/5f25c089cb34db4db112556f23c50d12da81b297

3fb4268b

Diff

@@ -127,10 +127,10 @@ theorem isMatching_iff_forall_degree {M : Subgraph G} [∀ v : V, Fintype (M.nei
 theorem IsMatching.even_card {M : Subgraph G} [Fintype M.verts] (h : M.IsMatching) :
     Even M.verts.toFinset.card := by
   classical
-    rw [is_matching_iff_forall_degree] at h 
-    use M.coe.edge_finset.card
-    rw [← two_mul, ← M.coe.sum_degrees_eq_twice_card_edges]
-    simp [h, Finset.card_univ]
+  rw [is_matching_iff_forall_degree] at h 
+  use M.coe.edge_finset.card
+  rw [← two_mul, ← M.coe.sum_degrees_eq_twice_card_edges]
+  simp [h, Finset.card_univ]
 #align simple_graph.subgraph.is_matching.even_card SimpleGraph.Subgraph.IsMatching.even_card
 -/

31ca6f9c

bump to nightly-2023-06-01-16

mathlib commit https://github.com/leanprover-community/mathlib/commit/cca40788df1b8755d5baf17ab2f27dacc2e17acb

b9c87c70

Diff

@@ -127,7 +127,7 @@ theorem isMatching_iff_forall_degree {M : Subgraph G} [∀ v : V, Fintype (M.nei
 theorem IsMatching.even_card {M : Subgraph G} [Fintype M.verts] (h : M.IsMatching) :
     Even M.verts.toFinset.card := by
   classical
-    rw [is_matching_iff_forall_degree] at h
+    rw [is_matching_iff_forall_degree] at h 
     use M.coe.edge_finset.card
     rw [← two_mul, ← M.coe.sum_degrees_eq_twice_card_edges]
     simp [h, Finset.card_univ]

31ca6f9c

bump to nightly-2023-04-04-02

mathlib commit https://github.com/leanprover-community/mathlib/commit/3cacc945118c8c637d89950af01da78307f59325

2ee17135

Diff

@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Alena Gusakov, Arthur Paulino, Kyle Miller
 
 ! This file was ported from Lean 3 source module combinatorics.simple_graph.matching
-! leanprover-community/mathlib commit 138448ae98f529ef34eeb61114191975ee2ca508
+! leanprover-community/mathlib commit 31ca6f9cf5f90a6206092cd7f84b359dcb6d52e0
 ! Please do not edit these lines, except to modify the commit id
 ! if you have ported upstream changes.
 -/
@@ -14,6 +14,9 @@ import Mathbin.Combinatorics.SimpleGraph.Subgraph
 /-!
 # Matchings
 
+> THIS FILE IS SYNCHRONIZED WITH MATHLIB4.
+> Any changes to this file require a corresponding PR to mathlib4.
+
 A *matching* for a simple graph is a set of disjoint pairs of adjacent vertices, and the set of all
 the vertices in a matching is called its *support* (and sometimes the vertices in the support are
 said to be *saturated* by the matching). A *perfect matching* is a matching whose support contains

138448ae

bump to nightly-2023-03-27-14

mathlib commit https://github.com/leanprover-community/mathlib/commit/ce86f4e05e9a9b8da5e316b22c76ce76440c56a1

b92a7b6a

Diff

@@ -51,6 +51,7 @@ variable {V : Type u} {G : SimpleGraph V} (M : Subgraph G)
 
 namespace Subgraph
 
+#print SimpleGraph.Subgraph.IsMatching /-
 /--
 The subgraph `M` of `G` is a matching if every vertex of `M` is incident to exactly one edge in `M`.
 We say that the vertices in `M.support` are *matched* or *saturated*.
@@ -58,13 +59,17 @@ We say that the vertices in `M.support` are *matched* or *saturated*.
 def IsMatching : Prop :=
   ∀ ⦃v⦄, v ∈ M.verts → ∃! w, M.Adj v w
 #align simple_graph.subgraph.is_matching SimpleGraph.Subgraph.IsMatching
+-/
 
+#print SimpleGraph.Subgraph.IsMatching.toEdge /-
 /-- Given a vertex, returns the unique edge of the matching it is incident to. -/
 noncomputable def IsMatching.toEdge {M : Subgraph G} (h : M.IsMatching) (v : M.verts) :
     M.edgeSetEmbedding :=
   ⟨⟦(v, (h v.property).some)⟧, (h v.property).choose_spec.1⟩
 #align simple_graph.subgraph.is_matching.to_edge SimpleGraph.Subgraph.IsMatching.toEdge
+-/
 
+#print SimpleGraph.Subgraph.IsMatching.toEdge_eq_of_adj /-
 theorem IsMatching.toEdge_eq_of_adj {M : Subgraph G} (h : M.IsMatching) {v w : V} (hv : v ∈ M.verts)
     (hvw : M.Adj v w) : h.toEdge ⟨v, hv⟩ = ⟨⟦(v, w)⟧, hvw⟩ :=
   by
@@ -72,38 +77,50 @@ theorem IsMatching.toEdge_eq_of_adj {M : Subgraph G} (h : M.IsMatching) {v w : V
   congr
   exact ((h (M.edge_vert hvw)).choose_spec.2 w hvw).symm
 #align simple_graph.subgraph.is_matching.to_edge_eq_of_adj SimpleGraph.Subgraph.IsMatching.toEdge_eq_of_adj
+-/
 
+#print SimpleGraph.Subgraph.IsMatching.toEdge.surjective /-
 theorem IsMatching.toEdge.surjective {M : Subgraph G} (h : M.IsMatching) :
     Function.Surjective h.toEdge := by
   rintro ⟨e, he⟩
   refine' Sym2.ind (fun x y he => _) e he
   exact ⟨⟨x, M.edge_vert he⟩, h.to_edge_eq_of_adj _ he⟩
 #align simple_graph.subgraph.is_matching.to_edge.surjective SimpleGraph.Subgraph.IsMatching.toEdge.surjective
+-/
 
+#print SimpleGraph.Subgraph.IsMatching.toEdge_eq_toEdge_of_adj /-
 theorem IsMatching.toEdge_eq_toEdge_of_adj {M : Subgraph G} {v w : V} (h : M.IsMatching)
     (hv : v ∈ M.verts) (hw : w ∈ M.verts) (ha : M.Adj v w) : h.toEdge ⟨v, hv⟩ = h.toEdge ⟨w, hw⟩ :=
   by
   rw [h.to_edge_eq_of_adj hv ha, h.to_edge_eq_of_adj hw (M.symm ha), Subtype.mk_eq_mk, Sym2.eq_swap]
 #align simple_graph.subgraph.is_matching.to_edge_eq_to_edge_of_adj SimpleGraph.Subgraph.IsMatching.toEdge_eq_toEdge_of_adj
+-/
 
+#print SimpleGraph.Subgraph.IsPerfectMatching /-
 /-- The subgraph `M` of `G` is a perfect matching on `G` if it's a matching and every vertex `G` is
 matched.
 -/
 def IsPerfectMatching : Prop :=
   M.IsMatching ∧ M.IsSpanning
 #align simple_graph.subgraph.is_perfect_matching SimpleGraph.Subgraph.IsPerfectMatching
+-/
 
+#print SimpleGraph.Subgraph.IsMatching.support_eq_verts /-
 theorem IsMatching.support_eq_verts {M : Subgraph G} (h : M.IsMatching) : M.support = M.verts :=
   by
   refine' M.support_subset_verts.antisymm fun v hv => _
   obtain ⟨w, hvw, -⟩ := h hv
   exact ⟨_, hvw⟩
 #align simple_graph.subgraph.is_matching.support_eq_verts SimpleGraph.Subgraph.IsMatching.support_eq_verts
+-/
 
+#print SimpleGraph.Subgraph.isMatching_iff_forall_degree /-
 theorem isMatching_iff_forall_degree {M : Subgraph G} [∀ v : V, Fintype (M.neighborSet v)] :
     M.IsMatching ↔ ∀ v : V, v ∈ M.verts → M.degree v = 1 := by simpa [degree_eq_one_iff_unique_adj]
 #align simple_graph.subgraph.is_matching_iff_forall_degree SimpleGraph.Subgraph.isMatching_iff_forall_degree
+-/
 
+#print SimpleGraph.Subgraph.IsMatching.even_card /-
 theorem IsMatching.even_card {M : Subgraph G} [Fintype M.verts] (h : M.IsMatching) :
     Even M.verts.toFinset.card := by
   classical
@@ -112,7 +129,9 @@ theorem IsMatching.even_card {M : Subgraph G} [Fintype M.verts] (h : M.IsMatchin
     rw [← two_mul, ← M.coe.sum_degrees_eq_twice_card_edges]
     simp [h, Finset.card_univ]
 #align simple_graph.subgraph.is_matching.even_card SimpleGraph.Subgraph.IsMatching.even_card
+-/
 
+#print SimpleGraph.Subgraph.isPerfectMatching_iff /-
 theorem isPerfectMatching_iff : M.IsPerfectMatching ↔ ∀ v, ∃! w, M.Adj v w :=
   by
   refine' ⟨_, fun hm => ⟨fun v hv => hm v, fun v => _⟩⟩
@@ -121,15 +140,20 @@ theorem isPerfectMatching_iff : M.IsPerfectMatching ↔ ∀ v, ∃! w, M.Adj v w
   · obtain ⟨w, hw, -⟩ := hm v
     exact M.edge_vert hw
 #align simple_graph.subgraph.is_perfect_matching_iff SimpleGraph.Subgraph.isPerfectMatching_iff
+-/
 
+#print SimpleGraph.Subgraph.isPerfectMatching_iff_forall_degree /-
 theorem isPerfectMatching_iff_forall_degree {M : Subgraph G} [∀ v, Fintype (M.neighborSet v)] :
     M.IsPerfectMatching ↔ ∀ v, M.degree v = 1 := by
   simp [degree_eq_one_iff_unique_adj, is_perfect_matching_iff]
 #align simple_graph.subgraph.is_perfect_matching_iff_forall_degree SimpleGraph.Subgraph.isPerfectMatching_iff_forall_degree
+-/
 
+#print SimpleGraph.Subgraph.IsPerfectMatching.even_card /-
 theorem IsPerfectMatching.even_card {M : Subgraph G} [Fintype V] (h : M.IsPerfectMatching) :
     Even (Fintype.card V) := by classical simpa [h.2.card_verts] using is_matching.even_card h.1
 #align simple_graph.subgraph.is_perfect_matching.even_card SimpleGraph.Subgraph.IsPerfectMatching.even_card
+-/
 
 end Subgraph

138448ae

bump to nightly-2023-02-25-00

mathlib commit https://github.com/leanprover-community/mathlib/commit/22131150f88a2d125713ffa0f4693e3355b1eb49

aca219f8

Diff

@@ -60,7 +60,8 @@ def IsMatching : Prop :=
 #align simple_graph.subgraph.is_matching SimpleGraph.Subgraph.IsMatching
 
 /-- Given a vertex, returns the unique edge of the matching it is incident to. -/
-noncomputable def IsMatching.toEdge {M : Subgraph G} (h : M.IsMatching) (v : M.verts) : M.edgeSet :=
+noncomputable def IsMatching.toEdge {M : Subgraph G} (h : M.IsMatching) (v : M.verts) :
+    M.edgeSetEmbedding :=
   ⟨⟦(v, (h v.property).some)⟧, (h v.property).choose_spec.1⟩
 #align simple_graph.subgraph.is_matching.to_edge SimpleGraph.Subgraph.IsMatching.toEdge

138448ae

bump to nightly-2023-02-21-16

mathlib commit https://github.com/leanprover-community/mathlib/commit/bd9851ca476957ea4549eb19b40e7b5ade9428cc

1107b979

Changes in mathlib4

mathlib3

mathlib4

138448ae

refactor: remove Sym2's global Prod setoid instance, use s(x, y) notation for unordered pairs (#8729)

The Sym2 type used a global setoid instance on α × α so that ⟦(x, y)⟧ could stand for an unordered pair using standard Quotient syntax. This commit refactors Sym2 to not use Quotient and instead use its own s(x, y) notation. One benefit to this is that this notation produces a term with type Sym2 rather than Quotient.

The Fintype instance for Sym2 is in Mathlib.Data.Finset.Sym. We switch from using the one for Quotient because it does not require DecidableEq.

9ed6b90f

Diff

@@ -57,11 +57,11 @@ def IsMatching : Prop := ∀ ⦃v⦄, v ∈ M.verts → ∃! w, M.Adj v w
 
 /-- Given a vertex, returns the unique edge of the matching it is incident to. -/
 noncomputable def IsMatching.toEdge {M : Subgraph G} (h : M.IsMatching) (v : M.verts) : M.edgeSet :=
-  ⟨⟦(v, (h v.property).choose)⟧, (h v.property).choose_spec.1⟩
+  ⟨s(v, (h v.property).choose), (h v.property).choose_spec.1⟩
 #align simple_graph.subgraph.is_matching.to_edge SimpleGraph.Subgraph.IsMatching.toEdge
 
 theorem IsMatching.toEdge_eq_of_adj {M : Subgraph G} (h : M.IsMatching) {v w : V} (hv : v ∈ M.verts)
-    (hvw : M.Adj v w) : h.toEdge ⟨v, hv⟩ = ⟨⟦(v, w)⟧, hvw⟩ := by
+    (hvw : M.Adj v w) : h.toEdge ⟨v, hv⟩ = ⟨s(v, w), hvw⟩ := by
   simp only [IsMatching.toEdge, Subtype.mk_eq_mk]
   congr
   exact ((h (M.edge_vert hvw)).choose_spec.2 w hvw).symm

138448ae

chore: script to replace headers with #align_import statements (#5979)

depends on: #5966

Co-authored-by: Eric Wieser <wieser.eric@gmail.com> Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

89aa3a3b

Diff

@@ -2,15 +2,12 @@
 Copyright (c) 2020 Alena Gusakov. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Alena Gusakov, Arthur Paulino, Kyle Miller
-
-! This file was ported from Lean 3 source module combinatorics.simple_graph.matching
-! leanprover-community/mathlib commit 138448ae98f529ef34eeb61114191975ee2ca508
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathlib.Combinatorics.SimpleGraph.DegreeSum
 import Mathlib.Combinatorics.SimpleGraph.Subgraph
 
+#align_import combinatorics.simple_graph.matching from "leanprover-community/mathlib"@"138448ae98f529ef34eeb61114191975ee2ca508"
+
 /-!
 # Matchings

138448ae

feat: port Combinatorics.SimpleGraph.Matching (#3071)

Co-authored-by: Moritz Firsching <firsching@google.com> Co-authored-by: Kyle Miller <kmill31415@gmail.com>

32663014

`combinatorics.simple_graph.matching` ⟷ `Mathlib.Combinatorics.SimpleGraph.Matching`

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

Dependencies 8 + 487

combinatorics.simple_graph.matching ⟷ Mathlib.Combinatorics.SimpleGraph.Matching

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

Dependencies 8 + 487

`combinatorics.simple_graph.matching` ⟷ `Mathlib.Combinatorics.SimpleGraph.Matching`