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

352ecfe1

(last sync)

Changes in mathlib3port

mathlib3

mathlib3port

f4758115

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) 2022 Kyle Miller. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Kyle Miller, Vincent Beffara
 -/
-import Mathbin.Combinatorics.SimpleGraph.Connectivity
-import Mathbin.Data.Nat.Lattice
+import Combinatorics.SimpleGraph.Connectivity
+import Data.Nat.Lattice
 
 #align_import combinatorics.simple_graph.metric from "leanprover-community/mathlib"@"f47581155c818e6361af4e4fda60d27d020c226b"

f4758115

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) 2022 Kyle Miller. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Kyle Miller, Vincent Beffara
-
-! This file was ported from Lean 3 source module combinatorics.simple_graph.metric
-! leanprover-community/mathlib commit f47581155c818e6361af4e4fda60d27d020c226b
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathbin.Combinatorics.SimpleGraph.Connectivity
 import Mathbin.Data.Nat.Lattice
 
+#align_import combinatorics.simple_graph.metric from "leanprover-community/mathlib"@"f47581155c818e6361af4e4fda60d27d020c226b"
+
 /-!
 # Graph metric

f4758115

bump to nightly-2023-05-28-03

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

6c6011cf

Diff

@@ -148,7 +148,6 @@ private theorem dist_comm_aux {u v : V} (h : G.Reachable u v) : G.dist u v ≤ G
   obtain ⟨p, hp⟩ := h.symm.exists_walk_of_dist
   rw [← hp, ← walk.length_reverse]
   apply dist_le
-#align simple_graph.dist_comm_aux simple_graph.dist_comm_aux
 
 #print SimpleGraph.dist_comm /-
 theorem dist_comm {u v : V} : G.dist u v = G.dist v u :=

f4758115

bump to nightly-2023-05-14-08

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

d31da313

Diff

@@ -54,7 +54,7 @@ variable {V : Type _} (G : SimpleGraph V)
 /-- The distance between two vertices is the length of the shortest walk between them.
 If no such walk exists, this uses the junk value of `0`. -/
 noncomputable def dist (u v : V) : ℕ :=
-  infₛ (Set.range (Walk.length : G.Walk u v → ℕ))
+  sInf (Set.range (Walk.length : G.Walk u v → ℕ))
 #align simple_graph.dist SimpleGraph.dist
 -/
 
@@ -63,7 +63,7 @@ variable {G}
 #print SimpleGraph.Reachable.exists_walk_of_dist /-
 protected theorem Reachable.exists_walk_of_dist {u v : V} (hr : G.Reachable u v) :
     ∃ p : G.Walk u v, p.length = G.dist u v :=
-  Nat.infₛ_mem (Set.range_nonempty_iff_nonempty.mpr hr)
+  Nat.sInf_mem (Set.range_nonempty_iff_nonempty.mpr hr)
 #align simple_graph.reachable.exists_walk_of_dist SimpleGraph.Reachable.exists_walk_of_dist
 -/
 
@@ -76,14 +76,14 @@ protected theorem Connected.exists_walk_of_dist (hconn : G.Connected) (u v : V)
 
 #print SimpleGraph.dist_le /-
 theorem dist_le {u v : V} (p : G.Walk u v) : G.dist u v ≤ p.length :=
-  Nat.infₛ_le ⟨p, rfl⟩
+  Nat.sInf_le ⟨p, rfl⟩
 #align simple_graph.dist_le SimpleGraph.dist_le
 -/
 
 #print SimpleGraph.dist_eq_zero_iff_eq_or_not_reachable /-
 @[simp]
 theorem dist_eq_zero_iff_eq_or_not_reachable {u v : V} :
-    G.dist u v = 0 ↔ u = v ∨ ¬G.Reachable u v := by simp [dist, Nat.infₛ_eq_zero, reachable]
+    G.dist u v = 0 ↔ u = v ∨ ¬G.Reachable u v := by simp [dist, Nat.sInf_eq_zero, reachable]
 #align simple_graph.dist_eq_zero_iff_eq_or_not_reachable SimpleGraph.dist_eq_zero_iff_eq_or_not_reachable
 -/
 
@@ -128,7 +128,7 @@ theorem dist_eq_zero_of_not_reachable {u v : V} (h : ¬G.Reachable u v) : G.dist
 theorem nonempty_of_pos_dist {u v : V} (h : 0 < G.dist u v) :
     (Set.univ : Set (G.Walk u v)).Nonempty := by
   simpa [Set.range_nonempty_iff_nonempty, Set.nonempty_iff_univ_nonempty] using
-    Nat.nonempty_of_pos_infₛ h
+    Nat.nonempty_of_pos_sInf h
 #align simple_graph.nonempty_of_pos_dist SimpleGraph.nonempty_of_pos_dist
 -/

f4758115

bump to nightly-2023-03-09-03

mathlib commit https://github.com/leanprover-community/mathlib/commit/21e3562c5e12d846c7def5eff8cdbc520d7d4936

061741a1

Diff

@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Kyle Miller, Vincent Beffara
 
 ! This file was ported from Lean 3 source module combinatorics.simple_graph.metric
-! leanprover-community/mathlib commit 352ecfe114946c903338006dd3287cb5a9955ff2
+! leanprover-community/mathlib commit f47581155c818e6361af4e4fda60d27d020c226b
 ! Please do not edit these lines, except to modify the commit id
 ! if you have ported upstream changes.
 -/
@@ -14,6 +14,9 @@ import Mathbin.Data.Nat.Lattice
 /-!
 # Graph metric
 
+> THIS FILE IS SYNCHRONIZED WITH MATHLIB4.
+> Any changes to this file require a corresponding PR to mathlib4.
+
 This module defines the `simple_graph.dist` function, which takes
 pairs of vertices to the length of the shortest walk between them.

352ecfe1

bump to nightly-2023-03-02-10

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

01978261

Diff

@@ -47,64 +47,89 @@ variable {V : Type _} (G : SimpleGraph V)
 /-! ## Metric -/
 
 
+#print SimpleGraph.dist /-
 /-- The distance between two vertices is the length of the shortest walk between them.
 If no such walk exists, this uses the junk value of `0`. -/
 noncomputable def dist (u v : V) : ℕ :=
   infₛ (Set.range (Walk.length : G.Walk u v → ℕ))
 #align simple_graph.dist SimpleGraph.dist
+-/
 
 variable {G}
 
+#print SimpleGraph.Reachable.exists_walk_of_dist /-
 protected theorem Reachable.exists_walk_of_dist {u v : V} (hr : G.Reachable u v) :
     ∃ p : G.Walk u v, p.length = G.dist u v :=
   Nat.infₛ_mem (Set.range_nonempty_iff_nonempty.mpr hr)
 #align simple_graph.reachable.exists_walk_of_dist SimpleGraph.Reachable.exists_walk_of_dist
+-/
 
+#print SimpleGraph.Connected.exists_walk_of_dist /-
 protected theorem Connected.exists_walk_of_dist (hconn : G.Connected) (u v : V) :
     ∃ p : G.Walk u v, p.length = G.dist u v :=
   (hconn u v).exists_walk_of_dist
 #align simple_graph.connected.exists_walk_of_dist SimpleGraph.Connected.exists_walk_of_dist
+-/
 
+#print SimpleGraph.dist_le /-
 theorem dist_le {u v : V} (p : G.Walk u v) : G.dist u v ≤ p.length :=
   Nat.infₛ_le ⟨p, rfl⟩
 #align simple_graph.dist_le SimpleGraph.dist_le
+-/
 
+#print SimpleGraph.dist_eq_zero_iff_eq_or_not_reachable /-
 @[simp]
 theorem dist_eq_zero_iff_eq_or_not_reachable {u v : V} :
     G.dist u v = 0 ↔ u = v ∨ ¬G.Reachable u v := by simp [dist, Nat.infₛ_eq_zero, reachable]
 #align simple_graph.dist_eq_zero_iff_eq_or_not_reachable SimpleGraph.dist_eq_zero_iff_eq_or_not_reachable
+-/
 
+#print SimpleGraph.dist_self /-
 theorem dist_self {v : V} : dist G v v = 0 := by simp
 #align simple_graph.dist_self SimpleGraph.dist_self
+-/
 
+#print SimpleGraph.Reachable.dist_eq_zero_iff /-
 protected theorem Reachable.dist_eq_zero_iff {u v : V} (hr : G.Reachable u v) :
     G.dist u v = 0 ↔ u = v := by simp [hr]
 #align simple_graph.reachable.dist_eq_zero_iff SimpleGraph.Reachable.dist_eq_zero_iff
+-/
 
+#print SimpleGraph.Reachable.pos_dist_of_ne /-
 protected theorem Reachable.pos_dist_of_ne {u v : V} (h : G.Reachable u v) (hne : u ≠ v) :
     0 < G.dist u v :=
   Nat.pos_of_ne_zero (by simp [h, hne])
 #align simple_graph.reachable.pos_dist_of_ne SimpleGraph.Reachable.pos_dist_of_ne
+-/
 
+#print SimpleGraph.Connected.dist_eq_zero_iff /-
 protected theorem Connected.dist_eq_zero_iff (hconn : G.Connected) {u v : V} :
     G.dist u v = 0 ↔ u = v := by simp [hconn u v]
 #align simple_graph.connected.dist_eq_zero_iff SimpleGraph.Connected.dist_eq_zero_iff
+-/
 
+#print SimpleGraph.Connected.pos_dist_of_ne /-
 protected theorem Connected.pos_dist_of_ne {u v : V} (hconn : G.Connected) (hne : u ≠ v) :
     0 < G.dist u v :=
   Nat.pos_of_ne_zero (by simp [hconn.dist_eq_zero_iff, hne])
 #align simple_graph.connected.pos_dist_of_ne SimpleGraph.Connected.pos_dist_of_ne
+-/
 
+#print SimpleGraph.dist_eq_zero_of_not_reachable /-
 theorem dist_eq_zero_of_not_reachable {u v : V} (h : ¬G.Reachable u v) : G.dist u v = 0 := by
   simp [h]
 #align simple_graph.dist_eq_zero_of_not_reachable SimpleGraph.dist_eq_zero_of_not_reachable
+-/
 
+#print SimpleGraph.nonempty_of_pos_dist /-
 theorem nonempty_of_pos_dist {u v : V} (h : 0 < G.dist u v) :
     (Set.univ : Set (G.Walk u v)).Nonempty := by
   simpa [Set.range_nonempty_iff_nonempty, Set.nonempty_iff_univ_nonempty] using
     Nat.nonempty_of_pos_infₛ h
 #align simple_graph.nonempty_of_pos_dist SimpleGraph.nonempty_of_pos_dist
+-/
 
+#print SimpleGraph.Connected.dist_triangle /-
 protected theorem Connected.dist_triangle (hconn : G.Connected) {u v w : V} :
     G.dist u w ≤ G.dist u v + G.dist v w :=
   by
@@ -113,6 +138,7 @@ protected theorem Connected.dist_triangle (hconn : G.Connected) {u v w : V} :
   rw [← hp, ← hq, ← walk.length_append]
   apply dist_le
 #align simple_graph.connected.dist_triangle SimpleGraph.Connected.dist_triangle
+-/
 
 private theorem dist_comm_aux {u v : V} (h : G.Reachable u v) : G.dist u v ≤ G.dist v u :=
   by
@@ -121,6 +147,7 @@ private theorem dist_comm_aux {u v : V} (h : G.Reachable u v) : G.dist u v ≤ G
   apply dist_le
 #align simple_graph.dist_comm_aux simple_graph.dist_comm_aux
 
+#print SimpleGraph.dist_comm /-
 theorem dist_comm {u v : V} : G.dist u v = G.dist v u :=
   by
   by_cases h : G.reachable u v
@@ -128,6 +155,7 @@ theorem dist_comm {u v : V} : G.dist u v = G.dist v u :=
   · have h' : ¬G.reachable v u := fun h' => absurd h'.symm h
     simp [h, h', dist_eq_zero_of_not_reachable]
 #align simple_graph.dist_comm SimpleGraph.dist_comm
+-/
 
 end SimpleGraph

352ecfe1

bump to nightly-2023-02-21-16

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

1107b979

Changes in mathlib4

mathlib3

mathlib4

352ecfe1

feat(Combinatorics/SimpleGraph): Existence of a path from u to v of length equal to G.dist u v (#11814)

Checkout this conversation on zulip. Co-authored-by: Kyle Miller [kmill31415@gmail.com](mailto:kmill31415@gmail.com)

Co-authored-by: Rida Hamadani <106540880+Rida-Hamadani@users.noreply.github.com>

2e8aeee4

Diff

@@ -122,4 +122,25 @@ theorem dist_comm {u v : V} : G.dist u v = G.dist v u := by
     simp [h, h', dist_eq_zero_of_not_reachable]
 #align simple_graph.dist_comm SimpleGraph.dist_comm
 
+theorem Walk.isPath_of_length_eq_dist {u v : V} (p : G.Walk u v) (hp : p.length = G.dist u v) :
+    p.IsPath := by
+  classical
+  have : p.bypass = p := by
+    apply Walk.bypass_eq_self_of_length_le
+    calc p.length
+      _ = G.dist u v := hp
+      _ ≤ p.bypass.length := dist_le p.bypass
+  rw [← this]
+  apply Walk.bypass_isPath
+
+lemma Reachable.exists_path_of_dist {u v : V} (hr : G.Reachable u v) :
+    ∃ (p : G.Walk u v), p.IsPath ∧ p.length = G.dist u v := by
+  obtain ⟨p, h⟩ := hr.exists_walk_of_dist
+  exact ⟨p, p.isPath_of_length_eq_dist h, h⟩
+
+lemma Connected.exists_path_of_dist (hconn : G.Connected) (u v : V) :
+    ∃ (p : G.Walk u v), p.IsPath ∧ p.length = G.dist u v := by
+  obtain ⟨p, h⟩ := hconn.exists_walk_of_dist u v
+  exact ⟨p, p.isPath_of_length_eq_dist h, h⟩
+
 end SimpleGraph

352ecfe1

chore: banish Type _ and Sort _ (#6499)

We remove all possible occurences of Type _ and Sort _ in favor of Type* and Sort*.

This has nice performance benefits.

32de3f67

Diff

@@ -39,7 +39,7 @@ graph metric, distance
 
 namespace SimpleGraph
 
-variable {V : Type _} (G : SimpleGraph V)
+variable {V : Type*} (G : SimpleGraph V)
 
 /-! ## Metric -/

352ecfe1

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) 2022 Kyle Miller. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Kyle Miller, Vincent Beffara
-
-! This file was ported from Lean 3 source module combinatorics.simple_graph.metric
-! leanprover-community/mathlib commit 352ecfe114946c903338006dd3287cb5a9955ff2
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathlib.Combinatorics.SimpleGraph.Connectivity
 import Mathlib.Data.Nat.Lattice
 
+#align_import combinatorics.simple_graph.metric from "leanprover-community/mathlib"@"352ecfe114946c903338006dd3287cb5a9955ff2"
+
 /-!
 # Graph metric

352ecfe1

chore: Rename to sSup/iSup (#3938)

As discussed on Zulip

Renames

supₛ → sSup
infₛ → sInf
supᵢ → iSup
infᵢ → iInf
bsupₛ → bsSup
binfₛ → bsInf
bsupᵢ → biSup
binfᵢ → biInf
csupₛ → csSup
cinfₛ → csInf
csupᵢ → ciSup
cinfᵢ → ciInf
unionₛ → sUnion
interₛ → sInter
unionᵢ → iUnion
interᵢ → iInter
bunionₛ → bsUnion
binterₛ → bsInter
bunionᵢ → biUnion
binterᵢ → biInter

Co-authored-by: Parcly Taxel <reddeloostw@gmail.com>

d1eb6264

Diff

@@ -50,14 +50,14 @@ variable {V : Type _} (G : SimpleGraph V)
 /-- The distance between two vertices is the length of the shortest walk between them.
 If no such walk exists, this uses the junk value of `0`. -/
 noncomputable def dist (u v : V) : ℕ :=
-  infₛ (Set.range (Walk.length : G.Walk u v → ℕ))
+  sInf (Set.range (Walk.length : G.Walk u v → ℕ))
 #align simple_graph.dist SimpleGraph.dist
 
 variable {G}
 
 protected theorem Reachable.exists_walk_of_dist {u v : V} (hr : G.Reachable u v) :
     ∃ p : G.Walk u v, p.length = G.dist u v :=
-  Nat.infₛ_mem (Set.range_nonempty_iff_nonempty.mpr hr)
+  Nat.sInf_mem (Set.range_nonempty_iff_nonempty.mpr hr)
 #align simple_graph.reachable.exists_walk_of_dist SimpleGraph.Reachable.exists_walk_of_dist
 
 protected theorem Connected.exists_walk_of_dist (hconn : G.Connected) (u v : V) :
@@ -66,12 +66,12 @@ protected theorem Connected.exists_walk_of_dist (hconn : G.Connected) (u v : V)
 #align simple_graph.connected.exists_walk_of_dist SimpleGraph.Connected.exists_walk_of_dist
 
 theorem dist_le {u v : V} (p : G.Walk u v) : G.dist u v ≤ p.length :=
-  Nat.infₛ_le ⟨p, rfl⟩
+  Nat.sInf_le ⟨p, rfl⟩
 #align simple_graph.dist_le SimpleGraph.dist_le
 
 @[simp]
 theorem dist_eq_zero_iff_eq_or_not_reachable {u v : V} :
-    G.dist u v = 0 ↔ u = v ∨ ¬G.Reachable u v := by simp [dist, Nat.infₛ_eq_zero, Reachable]
+    G.dist u v = 0 ↔ u = v ∨ ¬G.Reachable u v := by simp [dist, Nat.sInf_eq_zero, Reachable]
 #align simple_graph.dist_eq_zero_iff_eq_or_not_reachable SimpleGraph.dist_eq_zero_iff_eq_or_not_reachable
 
 theorem dist_self {v : V} : dist G v v = 0 := by simp
@@ -102,7 +102,7 @@ theorem dist_eq_zero_of_not_reachable {u v : V} (h : ¬G.Reachable u v) : G.dist
 theorem nonempty_of_pos_dist {u v : V} (h : 0 < G.dist u v) :
     (Set.univ : Set (G.Walk u v)).Nonempty := by
   simpa [Set.range_nonempty_iff_nonempty, Set.nonempty_iff_univ_nonempty] using
-    Nat.nonempty_of_pos_infₛ h
+    Nat.nonempty_of_pos_sInf h
 #align simple_graph.nonempty_of_pos_dist SimpleGraph.nonempty_of_pos_dist
 
 protected theorem Connected.dist_triangle (hconn : G.Connected) {u v w : V} :

352ecfe1

feat: Port Combinatorics.SimpleGraph.Metric (#2572)

c97ad7df

`combinatorics.simple_graph.metric` ⟷ `Mathlib.Combinatorics.SimpleGraph.Metric`

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

Renames

Dependencies 7 + 240

combinatorics.simple_graph.metric ⟷ Mathlib.Combinatorics.SimpleGraph.Metric

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

Renames

Dependencies 7 + 240

`combinatorics.simple_graph.metric` ⟷ `Mathlib.Combinatorics.SimpleGraph.Metric`