combinatorics.simple_graph.partition | 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

2303b3e2

(last sync)

Changes in mathlib3port

mathlib3

mathlib3port

ee05e9ce

bump to nightly-2024-03-17-08

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

22f01ce4

Diff

@@ -111,7 +111,7 @@ theorem partOfVertex_ne_of_adj {v w : V} (h : G.Adj v w) : P.partOfVertex v ≠
   by
   intro hn
   have hw := P.mem_part_of_vertex w
-  rw [← hn] at hw 
+  rw [← hn] at hw
   exact P.independent _ (P.part_of_vertex_mem v) (P.mem_part_of_vertex v) hw (G.ne_of_adj h) h
 #align simple_graph.partition.part_of_vertex_ne_of_adj SimpleGraph.Partition.partOfVertex_ne_of_adj
 -/
@@ -166,7 +166,7 @@ theorem partitionable_iff_colorable {n : ℕ} : G.Partitionable n ↔ G.Colorabl
   constructor
   · rintro ⟨P, hf, h⟩
     haveI : Fintype P.parts := hf.fintype
-    rw [Set.Finite.card_toFinset] at h 
+    rw [Set.Finite.card_toFinset] at h
     apply P.to_colorable.mono h
   · rintro ⟨C⟩
     refine' ⟨C.to_partition, C.color_classes_finite, le_trans _ (Fintype.card_fin n).le⟩

ee05e9ce

bump to nightly-2024-01-17-06

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

8ba88f37

Diff

@@ -132,10 +132,10 @@ def toColoring' : G.Coloring (Set V) :=
 #align simple_graph.partition.to_coloring' SimpleGraph.Partition.toColoring'
 -/
 
-#print SimpleGraph.Partition.to_colorable /-
-theorem to_colorable [Fintype P.parts] : G.Colorable (Fintype.card P.parts) :=
-  P.toColoring.to_colorable
-#align simple_graph.partition.to_colorable SimpleGraph.Partition.to_colorable
+#print SimpleGraph.Partition.colorable /-
+theorem colorable [Fintype P.parts] : G.Colorable (Fintype.card P.parts) :=
+  P.toColoring.colorable
+#align simple_graph.partition.to_colorable SimpleGraph.Partition.colorable
 -/
 
 end Partition

ee05e9ce

bump to nightly-2023-09-24-06

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

5655435f

Diff

@@ -3,7 +3,7 @@ Copyright (c) 2021 Arthur Paulino. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Arthur Paulino, Kyle Miller
 -/
-import Mathbin.Combinatorics.SimpleGraph.Coloring
+import Combinatorics.SimpleGraph.Coloring
 
 #align_import combinatorics.simple_graph.partition from "leanprover-community/mathlib"@"ee05e9ce1322178f0c12004eb93c00d2c8c00ed2"

ee05e9ce

bump to nightly-2023-07-20-09

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

9c56d0dd

Diff

@@ -2,14 +2,11 @@
 Copyright (c) 2021 Arthur Paulino. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Arthur Paulino, Kyle Miller
-
-! This file was ported from Lean 3 source module combinatorics.simple_graph.partition
-! leanprover-community/mathlib commit ee05e9ce1322178f0c12004eb93c00d2c8c00ed2
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathbin.Combinatorics.SimpleGraph.Coloring
 
+#align_import combinatorics.simple_graph.partition from "leanprover-community/mathlib"@"ee05e9ce1322178f0c12004eb93c00d2c8c00ed2"
+
 /-!
 # Graph partitions

ee05e9ce

bump to nightly-2023-06-01-16

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

b9c87c70

Diff

@@ -114,7 +114,7 @@ theorem partOfVertex_ne_of_adj {v w : V} (h : G.Adj v w) : P.partOfVertex v ≠
   by
   intro hn
   have hw := P.mem_part_of_vertex w
-  rw [← hn] at hw
+  rw [← hn] at hw 
   exact P.independent _ (P.part_of_vertex_mem v) (P.mem_part_of_vertex v) hw (G.ne_of_adj h) h
 #align simple_graph.partition.part_of_vertex_ne_of_adj SimpleGraph.Partition.partOfVertex_ne_of_adj
 -/
@@ -169,7 +169,7 @@ theorem partitionable_iff_colorable {n : ℕ} : G.Partitionable n ↔ G.Colorabl
   constructor
   · rintro ⟨P, hf, h⟩
     haveI : Fintype P.parts := hf.fintype
-    rw [Set.Finite.card_toFinset] at h
+    rw [Set.Finite.card_toFinset] at h 
     apply P.to_colorable.mono h
   · rintro ⟨C⟩
     refine' ⟨C.to_partition, C.color_classes_finite, le_trans _ (Fintype.card_fin n).le⟩

ee05e9ce

bump to nightly-2023-05-28-04

mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb

6797a637

Diff

@@ -98,18 +98,14 @@ def partOfVertex (v : V) : Set V :=
 -/
 
 #print SimpleGraph.Partition.partOfVertex_mem /-
-theorem partOfVertex_mem (v : V) : P.partOfVertex v ∈ P.parts :=
-  by
-  obtain ⟨h, -⟩ := (P.is_partition.2 v).choose_spec.1
-  exact h
+theorem partOfVertex_mem (v : V) : P.partOfVertex v ∈ P.parts := by
+  obtain ⟨h, -⟩ := (P.is_partition.2 v).choose_spec.1; exact h
 #align simple_graph.partition.part_of_vertex_mem SimpleGraph.Partition.partOfVertex_mem
 -/
 
 #print SimpleGraph.Partition.mem_partOfVertex /-
-theorem mem_partOfVertex (v : V) : v ∈ P.partOfVertex v :=
-  by
-  obtain ⟨⟨h1, h2⟩, h3⟩ := (P.is_partition.2 v).choose_spec
-  exact h2.1
+theorem mem_partOfVertex (v : V) : v ∈ P.partOfVertex v := by
+  obtain ⟨⟨h1, h2⟩, h3⟩ := (P.is_partition.2 v).choose_spec; exact h2.1
 #align simple_graph.partition.mem_part_of_vertex SimpleGraph.Partition.mem_partOfVertex
 -/
 
@@ -127,10 +123,8 @@ theorem partOfVertex_ne_of_adj {v w : V} (h : G.Adj v w) : P.partOfVertex v ≠
 /-- Create a coloring using the parts themselves as the colors.
 Each vertex is colored by the part it's contained in. -/
 def toColoring : G.Coloring P.parts :=
-  Coloring.mk (fun v => ⟨P.partOfVertex v, P.partOfVertex_mem v⟩) fun _ _ hvw =>
-    by
-    rw [Ne.def, Subtype.mk_eq_mk]
-    exact P.part_of_vertex_ne_of_adj hvw
+  Coloring.mk (fun v => ⟨P.partOfVertex v, P.partOfVertex_mem v⟩) fun _ _ hvw => by
+    rw [Ne.def, Subtype.mk_eq_mk]; exact P.part_of_vertex_ne_of_adj hvw
 #align simple_graph.partition.to_coloring SimpleGraph.Partition.toColoring
 -/

ee05e9ce

bump to nightly-2023-03-02-03

mathlib commit https://github.com/leanprover-community/mathlib/commit/195fcd60ff2bfe392543bceb0ec2adcdb472db4c

db7421c3

Diff

@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Arthur Paulino, Kyle Miller
 
 ! This file was ported from Lean 3 source module combinatorics.simple_graph.partition
-! leanprover-community/mathlib commit 2303b3e299f1c75b07bceaaac130ce23044d1386
+! leanprover-community/mathlib commit ee05e9ce1322178f0c12004eb93c00d2c8c00ed2
 ! Please do not edit these lines, except to modify the commit id
 ! if you have ported upstream changes.
 -/
@@ -13,6 +13,9 @@ import Mathbin.Combinatorics.SimpleGraph.Coloring
 /-!
 # Graph partitions
 
+> THIS FILE IS SYNCHRONIZED WITH MATHLIB4.
+> Any changes to this file require a corresponding PR to mathlib4.
+
 This module provides an interface for dealing with partitions on simple graphs. A partition of
 a graph `G`, with vertices `V`, is a set `P` of disjoint nonempty subsets of `V` such that:

2303b3e2

bump to nightly-2023-02-28-14

mathlib commit https://github.com/leanprover-community/mathlib/commit/9da1b3534b65d9661eb8f42443598a92bbb49211

e879718a

Diff

@@ -54,6 +54,7 @@ namespace SimpleGraph
 
 variable {V : Type u} (G : SimpleGraph V)
 
+#print SimpleGraph.Partition /-
 /-- A `partition` of a simple graph `G` is a structure constituted by
 * `parts`: a set of subsets of the vertices `V` of `G`
 * `is_partition`: a proof that `parts` is a proper partition of `V`
@@ -64,40 +65,52 @@ structure Partition where
   IsPartition : Setoid.IsPartition parts
   Independent : ∀ s ∈ parts, IsAntichain G.Adj s
 #align simple_graph.partition SimpleGraph.Partition
+-/
 
+#print SimpleGraph.Partition.PartsCardLe /-
 /-- Whether a partition `P` has at most `n` parts. A graph with a partition
 satisfying this predicate called `n`-partite. (See `simple_graph.partitionable`.) -/
 def Partition.PartsCardLe {G : SimpleGraph V} (P : G.partitionₓ) (n : ℕ) : Prop :=
   ∃ h : P.parts.Finite, h.toFinset.card ≤ n
 #align simple_graph.partition.parts_card_le SimpleGraph.Partition.PartsCardLe
+-/
 
+#print SimpleGraph.Partitionable /-
 /-- Whether a graph is `n`-partite, which is whether its vertex set
 can be partitioned in at most `n` independent sets. -/
 def Partitionable (n : ℕ) : Prop :=
   ∃ P : G.partitionₓ, P.PartsCardLe n
 #align simple_graph.partitionable SimpleGraph.Partitionable
+-/
 
 namespace Partition
 
 variable {G} (P : G.partitionₓ)
 
+#print SimpleGraph.Partition.partOfVertex /-
 /-- The part in the partition that `v` belongs to -/
 def partOfVertex (v : V) : Set V :=
   Classical.choose (P.IsPartition.2 v)
 #align simple_graph.partition.part_of_vertex SimpleGraph.Partition.partOfVertex
+-/
 
+#print SimpleGraph.Partition.partOfVertex_mem /-
 theorem partOfVertex_mem (v : V) : P.partOfVertex v ∈ P.parts :=
   by
   obtain ⟨h, -⟩ := (P.is_partition.2 v).choose_spec.1
   exact h
 #align simple_graph.partition.part_of_vertex_mem SimpleGraph.Partition.partOfVertex_mem
+-/
 
+#print SimpleGraph.Partition.mem_partOfVertex /-
 theorem mem_partOfVertex (v : V) : v ∈ P.partOfVertex v :=
   by
   obtain ⟨⟨h1, h2⟩, h3⟩ := (P.is_partition.2 v).choose_spec
   exact h2.1
 #align simple_graph.partition.mem_part_of_vertex SimpleGraph.Partition.mem_partOfVertex
+-/
 
+#print SimpleGraph.Partition.partOfVertex_ne_of_adj /-
 theorem partOfVertex_ne_of_adj {v w : V} (h : G.Adj v w) : P.partOfVertex v ≠ P.partOfVertex w :=
   by
   intro hn
@@ -105,7 +118,9 @@ theorem partOfVertex_ne_of_adj {v w : V} (h : G.Adj v w) : P.partOfVertex v ≠
   rw [← hn] at hw
   exact P.independent _ (P.part_of_vertex_mem v) (P.mem_part_of_vertex v) hw (G.ne_of_adj h) h
 #align simple_graph.partition.part_of_vertex_ne_of_adj SimpleGraph.Partition.partOfVertex_ne_of_adj
+-/
 
+#print SimpleGraph.Partition.toColoring /-
 /-- Create a coloring using the parts themselves as the colors.
 Each vertex is colored by the part it's contained in. -/
 def toColoring : G.Coloring P.parts :=
@@ -114,20 +129,26 @@ def toColoring : G.Coloring P.parts :=
     rw [Ne.def, Subtype.mk_eq_mk]
     exact P.part_of_vertex_ne_of_adj hvw
 #align simple_graph.partition.to_coloring SimpleGraph.Partition.toColoring
+-/
 
+#print SimpleGraph.Partition.toColoring' /-
 /-- Like `simple_graph.partition.to_coloring` but uses `set V` as the coloring type. -/
 def toColoring' : G.Coloring (Set V) :=
   Coloring.mk P.partOfVertex fun _ _ hvw => P.partOfVertex_ne_of_adj hvw
 #align simple_graph.partition.to_coloring' SimpleGraph.Partition.toColoring'
+-/
 
+#print SimpleGraph.Partition.to_colorable /-
 theorem to_colorable [Fintype P.parts] : G.Colorable (Fintype.card P.parts) :=
   P.toColoring.to_colorable
 #align simple_graph.partition.to_colorable SimpleGraph.Partition.to_colorable
+-/
 
 end Partition
 
 variable {G}
 
+#print SimpleGraph.Coloring.toPartition /-
 /-- Creates a partition from a coloring. -/
 @[simps]
 def Coloring.toPartition {α : Type v} (C : G.Coloring α) : G.partitionₓ
@@ -138,12 +159,14 @@ def Coloring.toPartition {α : Type v} (C : G.Coloring α) : G.partitionₓ
     rintro s ⟨c, rfl⟩
     apply C.color_classes_independent
 #align simple_graph.coloring.to_partition SimpleGraph.Coloring.toPartition
+-/
 
 /-- The partition where every vertex is in its own part. -/
 @[simps]
 instance : Inhabited (Partition G) :=
   ⟨G.selfColoring.toPartition⟩
 
+#print SimpleGraph.partitionable_iff_colorable /-
 theorem partitionable_iff_colorable {n : ℕ} : G.Partitionable n ↔ G.Colorable n :=
   by
   constructor
@@ -158,6 +181,7 @@ theorem partitionable_iff_colorable {n : ℕ} : G.Partitionable n ↔ G.Colorabl
     rw [h.card_to_finset]
     exact C.card_color_classes_le
 #align simple_graph.partitionable_iff_colorable SimpleGraph.partitionable_iff_colorable
+-/
 
 end SimpleGraph

2303b3e2

bump to nightly-2023-02-21-16

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

1107b979

Changes in mathlib4

mathlib3

mathlib4

2303b3e2

feat: make generalize_proofs handle proofs under binders (#12472)

The generalize_proofs tactic had a bug where it would not generalize proofs that appeared under binders correctly, creating terms with fvars from the wrong context. The tactic has been refactored, and it now abstracts the proofs (universally quantifying all the bound variables that appear in the proof) before lifting them to the local context.

This feature can be controlled with the abstract option. Using generalize_proofs (config := { abstract := false }) turns off proof abstraction and leaves alone those proofs that refer to bound variables.

Other new features:

generalize_proofs at h for a let-bound local hypothesis h will clear its value.
generalize_proofs at h for a duplicate proposition will eliminate h from the local context.
Proofs are recursively generalized for each new local hypothesis. This can be turned off with generalize_proofs (config := { maxDepth := 0 }).
generalize_proofs at h will no longer generalize proofs from the goal.
The type of the generalized proof is carefully computed by propagating expected types, rather than by using inferType. This gives local hypotheses in more useful forms.

(This PR serves as a followup to this comment.)

32616bea

Diff

@@ -147,7 +147,8 @@ theorem partitionable_iff_colorable {n : ℕ} : G.Partitionable n ↔ G.Colorabl
   · rintro ⟨C⟩
     refine' ⟨C.toPartition, C.colorClasses_finite, le_trans _ (Fintype.card_fin n).le⟩
     generalize_proofs h
-    haveI : Fintype C.colorClasses := C.colorClasses_finite.fintype
+    change Set.Finite (Coloring.colorClasses C) at h
+    have : Fintype C.colorClasses := C.colorClasses_finite.fintype
     rw [h.card_toFinset]
     exact C.card_colorClasses_le
 #align simple_graph.partitionable_iff_colorable SimpleGraph.partitionable_iff_colorable

2303b3e2

feat: ∃! x ∈ s, p x syntax (#12237)

More generally, adds a binderPred variant for ExistsUnique.

Uses this syntax to clean up Mathlib.Data.Setoid.Partition and remove Mathport warnings.

2dac82fe

Diff

@@ -91,8 +91,8 @@ theorem partOfVertex_mem (v : V) : P.partOfVertex v ∈ P.parts := by
 #align simple_graph.partition.part_of_vertex_mem SimpleGraph.Partition.partOfVertex_mem
 
 theorem mem_partOfVertex (v : V) : v ∈ P.partOfVertex v := by
-  obtain ⟨⟨h1, h2⟩, _h3⟩ := (P.isPartition.2 v).choose_spec
-  exact h2.1
+  obtain ⟨⟨_, h⟩, _⟩ := (P.isPartition.2 v).choose_spec
+  exact h
 #align simple_graph.partition.mem_part_of_vertex SimpleGraph.Partition.mem_partOfVertex
 
 theorem partOfVertex_ne_of_adj {v w : V} (h : G.Adj v w) : P.partOfVertex v ≠ P.partOfVertex w := by

2303b3e2

chore: avoid Ne.def (adaptation for nightly-2024-03-27) (#11801)

1b40c7bc

Diff

@@ -106,7 +106,7 @@ theorem partOfVertex_ne_of_adj {v w : V} (h : G.Adj v w) : P.partOfVertex v ≠
 Each vertex is colored by the part it's contained in. -/
 def toColoring : G.Coloring P.parts :=
   Coloring.mk (fun v ↦ ⟨P.partOfVertex v, P.partOfVertex_mem v⟩) fun hvw ↦ by
-    rw [Ne.def, Subtype.mk_eq_mk]
+    rw [Ne, Subtype.mk_eq_mk]
     exact P.partOfVertex_ne_of_adj hvw
 #align simple_graph.partition.to_coloring SimpleGraph.Partition.toColoring

2303b3e2

refactor: make SimpleGraph.chromaticNumber be ENat-valued (#8883)

This removes an awkwardness of the API, where theorems had to include colorability hypotheses. This trades that awkwardness for a smaller one, which is that one writes G.Colorable (ENat.toNat G.chromaticNumber) rather than G.Colorable G.chromaticNumber.

It would be good to have a followup refactoring PR to more carefully evaluate the API after this change.

59641348

Diff

@@ -115,9 +115,9 @@ def toColoring' : G.Coloring (Set V) :=
   Coloring.mk P.partOfVertex fun hvw ↦ P.partOfVertex_ne_of_adj hvw
 #align simple_graph.partition.to_coloring' SimpleGraph.Partition.toColoring'
 
-theorem to_colorable [Fintype P.parts] : G.Colorable (Fintype.card P.parts) :=
-  P.toColoring.to_colorable
-#align simple_graph.partition.to_colorable SimpleGraph.Partition.to_colorable
+theorem colorable [Fintype P.parts] : G.Colorable (Fintype.card P.parts) :=
+  P.toColoring.colorable
+#align simple_graph.partition.to_colorable SimpleGraph.Partition.colorable
 
 end Partition
 
@@ -143,7 +143,7 @@ theorem partitionable_iff_colorable {n : ℕ} : G.Partitionable n ↔ G.Colorabl
   · rintro ⟨P, hf, hc⟩
     have : Fintype P.parts := hf.fintype
     rw [Set.Finite.card_toFinset hf] at hc
-    apply P.to_colorable.mono hc
+    apply P.colorable.mono hc
   · rintro ⟨C⟩
     refine' ⟨C.toPartition, C.colorClasses_finite, le_trans _ (Fintype.card_fin n).le⟩
     generalize_proofs h

2303b3e2

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,14 +2,11 @@
 Copyright (c) 2021 Arthur Paulino. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Arthur Paulino, Kyle Miller
-
-! This file was ported from Lean 3 source module combinatorics.simple_graph.partition
-! leanprover-community/mathlib commit 2303b3e299f1c75b07bceaaac130ce23044d1386
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathlib.Combinatorics.SimpleGraph.Coloring
 
+#align_import combinatorics.simple_graph.partition from "leanprover-community/mathlib"@"2303b3e299f1c75b07bceaaac130ce23044d1386"
+
 /-!
 # Graph partitions

2303b3e2

chore: bye-bye, solo bys! (#3825)

This PR puts, with one exception, every single remaining by that lies all by itself on its own line to the previous line, thus matching the current behaviour of start-port.sh. The exception is when the by begins the second or later argument to a tuple or anonymous constructor; see https://github.com/leanprover-community/mathlib4/pull/3825#discussion_r1186702599.

Essentially this is s/\n *by$/ by/g, but with manual editing to satisfy the linter's max-100-char-line requirement. The Python style linter is also modified to catch these "isolated bys".

14167e48

Diff

@@ -108,8 +108,7 @@ theorem partOfVertex_ne_of_adj {v w : V} (h : G.Adj v w) : P.partOfVertex v ≠
 /-- Create a coloring using the parts themselves as the colors.
 Each vertex is colored by the part it's contained in. -/
 def toColoring : G.Coloring P.parts :=
-  Coloring.mk (fun v ↦ ⟨P.partOfVertex v, P.partOfVertex_mem v⟩) fun hvw ↦
-    by
+  Coloring.mk (fun v ↦ ⟨P.partOfVertex v, P.partOfVertex_mem v⟩) fun hvw ↦ by
     rw [Ne.def, Subtype.mk_eq_mk]
     exact P.partOfVertex_ne_of_adj hvw
 #align simple_graph.partition.to_coloring SimpleGraph.Partition.toColoring

2303b3e2

feat: port Combinatorics.SimpleGraph.Partition (#2536)

ea5eff7d

`combinatorics.simple_graph.partition` ⟷ `Mathlib.Combinatorics.SimpleGraph.Partition`

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

Dependencies 7 + 251

combinatorics.simple_graph.partition ⟷ Mathlib.Combinatorics.SimpleGraph.Partition

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

Dependencies 7 + 251

`combinatorics.simple_graph.partition` ⟷ `Mathlib.Combinatorics.SimpleGraph.Partition`