edge_arrival_prob_sum
For a simple graph G on vertex set Fin n with decidable adjacency and H : Finset (Sym2 (Fin n)), if H.card < G.edgeFinset.card and 0 < compatible_labelings G H, then the sum over e : Sym2 (Fin n) of (if e ∉ H ∧ 0 < compatible_labelings G (insert e H) then edge_arrival_prob G H e else 0) equals 1.
Statement
theorem edge_arrival_prob_sum {n : ℕ} (G : SimpleGraph (Fin n)) [DecidableRel G.Adj] (H : Finset (Sym2 (Fin n))) (hcard : H.card < G.edgeFinset.card) (hcomp : 0 < compatible_labelings G H) : ∑ e ∈ (Finset.univ : Finset (Sym2 (Fin n))), (if e ∉ H ∧ 0 < compatible_labelings G (insert e H) then edge_arrival_prob G H e else 0) = 1
- Source
- arXiv:2611.13571, Lemma 5.1 proof
- Verified
- 13 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- compatible_labelingsFor a simple graph G on vertex set Fin n with decidable adjacency, and a finite set H of observed edges (H : Finset (Sym2 (Fin n))),…
- edge_arrival_probFor a simple graph G on vertex set Fin n with decidable adjacency, a finite set H : Finset (Sym2 (Fin n)) of observed edges, and an edge e…
Read back from the Lean
Let $n$ be a natural number, $G$ be a simple graph on vertex set Fin n with decidable adjacency, and $H$ be a finite set of unordered pairs of vertices (Sym2 (Fin n)).
Assume:
1. hcard: the cardinality of $H$ is strictly less than the number of edges in $G$ (H.card < G.edgeFinset.card).
2. hcomp: the number of permutations $\pi$ of Fin n such that $H \subseteq (G.\text{map } \pi).\text{edgeFinset}$ is strictly greater than 0 (0 < compatible_labelings G H).
Then, the sum over all unordered pairs of vertices $e \in \text{Sym2}(\text{Fin } n)$ of:
- edge_arrival_prob G H e, if $e \notin H$ and 0 < compatible_labelings G (insert e H),
- and $0$ otherwise,
equals $1$ (in $\mathbb{R}$).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
Proof sketch: We want to show that the edge arrival probabilities sum to 1. By expressing the probabilities in terms of compatible labelings and exchanging the order of summation between edges and permutations (double counting), the sum of compatible labelings of H ∪ {e} over edges e ∉ H evaluates to (|E(G)| - |H|) times the number of compatible labelings of H. Dividing by the normalization constant gives 1.
Lemma 1
explanation
have := SimpleGraph.card_edgeFinset_map π.toEmbedding G convert thisLemma 2
explanation
have h1 : ∀ a, (t.filter (r a ·)).card = ∑ b ∈ t, if r a b then 1 else 0 := by intro a rw [← Finset.sum_filter] simp have h2 : ∀ b, (s.filter (r · b)).card = ∑ a ∈ s, if r a b then 1 else 0 := by intro b rw [← Finset.sum_filter] simp simp_rw [h1, h2] exact Finset.sum_comm
Lemma 3
explanation
have heq : ((Finset.univ.filter (fun e : Sym2 (Fin n) => e ∉ H)).filter (fun e => e ∈ (G.map π.toEmbedding).edgeFinset)) = (G.map π.toEmbedding).edgeFinset \ H := by ext e simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_sdiff] tauto rw [heq, Finset.card_sdiff_of_subset hH, edge_arrival_prob_sum_card_map_edges]
Lemma 4
explanation
let P := Finset.univ.filter (fun π : Equiv.Perm (Fin n) => H ⊆ (G.map π.toEmbedding).edgeFinset) have h1 : ∀ e, compatible_labelings G (insert e H) = (P.filter (fun π => e ∈ (G.map π.toEmbedding).edgeFinset)).card := by intro e unfold compatible_labelings apply congr_arg Finset.card ext π simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.insert_subset_iff, P] tauto simp_rw [h1] rw [edge_arrival_prob_sum_card_filter_eq] have h2 : ∀ π ∈ P, ((Finset.univ.filter (fun e : Sym2 (Fin n) => e ∉ H)).filter (fun e => e ∈ (G.map π.toEmbedding).edgeFinset)).card = G.edgeFinset.card - H.card := by intro π hπ have hH : H ⊆ (G.map π.toEmbedding).edgeFinset := (Finset.mem_filter.mp hπ).2 exact edge_arrival_prob_sum_filter_edges_diff G H π hH rw [Finset.sum_congr rfl h2, Finset.sum_const, nsmul_eq_mul] change P.card * (G.edgeFinset.card - H.card) = (G.edgeFinset.card - H.card) * compatible_labelings G H have : compatible_labelings G H = P.card := rfl rw [this, mul_comm]
Lemma 5
explanation
have hd : ((G.edgeFinset.card - H.card : ℝ) * (compatible_labelings G H : ℝ)) ≠ 0 := by have h1 : (G.edgeFinset.card - H.card : ℝ) ≠ 0 := by have : (H.card : ℝ) < G.edgeFinset.card := Nat.cast_lt.mpr hcard linarith have h2 : (compatible_labelings G H : ℝ) ≠ 0 := by have : 0 < (compatible_labelings G H : ℝ) := Nat.cast_pos.mpr hcomp linarith exact mul_ne_zero h1 h2 unfold edge_arrival_prob rw [if_neg hd] by_cases he : e ∈ H · rw [if_neg (fun h => h.1 he), if_neg (fun h => h he)] · rw [if_pos he] by_cases hc : 0 < compatible_labelings G (insert e H) · rw [if_pos ⟨he, hc⟩] · rw [if_neg (fun h => hc h.2)] have : compatible_labelings G (insert e H) = 0 := by omega rw [this, Nat.cast_zero, zero_div]
Theorem
explanation
have hd : ((G.edgeFinset.card - H.card : ℝ) * (compatible_labelings G H : ℝ)) ≠ 0 := by have h1 : (G.edgeFinset.card - H.card : ℝ) ≠ 0 := by have : (H.card : ℝ) < G.edgeFinset.card := Nat.cast_lt.mpr hcard linarith have h2 : (compatible_labelings G H : ℝ) ≠ 0 := by have : 0 < (compatible_labelings G H : ℝ) := Nat.cast_pos.mpr hcomp linarith exact mul_ne_zero h1 h2 simp_rw [edge_arrival_prob_sum_summand_eq G H hcard hcomp] rw [← Finset.sum_filter, ← Finset.sum_div, ← Nat.cast_sum] rw [edge_arrival_prob_sum_compatible_labelings_insert G H] push_cast rw [Nat.cast_sub (le_of_lt hcard)] exact div_self hd
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.
lemma edge_arrival_prob_sum_card_map_edges {n : ℕ} (G : SimpleGraph (Fin n)) [DecidableRel G.Adj] (π : Equiv.Perm (Fin n)) : (G.map π.toEmbedding).edgeFinset.card = G.edgeFinset.card := by have := SimpleGraph.card_edgeFinset_map π.toEmbedding G convert thislemma edge_arrival_prob_sum_card_filter_eq {α β : Type*} (s : Finset α) (t : Finset β) (r : α → β → Prop) [∀ a b, Decidable (r a b)] : (∑ a ∈ s, (t.filter (r a ·)).card : ℕ) = ∑ b ∈ t, (s.filter (r · b)).card := by have h1 : ∀ a, (t.filter (r a ·)).card = ∑ b ∈ t, if r a b then 1 else 0 := by intro a rw [← Finset.sum_filter] simp have h2 : ∀ b, (s.filter (r · b)).card = ∑ a ∈ s, if r a b then 1 else 0 := by intro b rw [← Finset.sum_filter] simp simp_rw [h1, h2] exact Finset.sum_commlemma edge_arrival_prob_sum_filter_edges_diff {n : ℕ} (G : SimpleGraph (Fin n)) [DecidableRel G.Adj] (H : Finset (Sym2 (Fin n))) (π : Equiv.Perm (Fin n)) (hH : H ⊆ (G.map π.toEmbedding).edgeFinset) : ((Finset.univ.filter (fun e : Sym2 (Fin n) => e ∉ H)).filter (fun e => e ∈ (G.map π.toEmbedding).edgeFinset)).card = G.edgeFinset.card - H.card := by have heq : ((Finset.univ.filter (fun e : Sym2 (Fin n) => e ∉ H)).filter (fun e => e ∈ (G.map π.toEmbedding).edgeFinset)) = (G.map π.toEmbedding).edgeFinset \ H := by ext e simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_sdiff] tauto rw [heq, Finset.card_sdiff_of_subset hH, edge_arrival_prob_sum_card_map_edges]lemma edge_arrival_prob_sum_compatible_labelings_insert {n : ℕ} (G : SimpleGraph (Fin n)) [DecidableRel G.Adj] (H : Finset (Sym2 (Fin n))) : ∑ e ∈ Finset.univ.filter (fun e : Sym2 (Fin n) => e ∉ H), compatible_labelings G (insert e H) = (G.edgeFinset.card - H.card) * compatible_labelings G H := by let P := Finset.univ.filter (fun π : Equiv.Perm (Fin n) => H ⊆ (G.map π.toEmbedding).edgeFinset) have h1 : ∀ e, compatible_labelings G (insert e H) = (P.filter (fun π => e ∈ (G.map π.toEmbedding).edgeFinset)).card := by intro e unfold compatible_labelings apply congr_arg Finset.card ext π simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.insert_subset_iff, P] tauto simp_rw [h1] rw [edge_arrival_prob_sum_card_filter_eq] have h2 : ∀ π ∈ P, ((Finset.univ.filter (fun e : Sym2 (Fin n) => e ∉ H)).filter (fun e => e ∈ (G.map π.toEmbedding).edgeFinset)).card = G.edgeFinset.card - H.card := by intro π hπ have hH : H ⊆ (G.map π.toEmbedding).edgeFinset := (Finset.mem_filter.mp hπ).2 exact edge_arrival_prob_sum_filter_edges_diff G H π hH rw [Finset.sum_congr rfl h2, Finset.sum_const, nsmul_eq_mul] change P.card * (G.edgeFinset.card - H.card) = (G.edgeFinset.card - H.card) * compatible_labelings G H have : compatible_labelings G H = P.card := rfl rw [this, mul_comm]lemma edge_arrival_prob_sum_summand_eq {n : ℕ} (G : SimpleGraph (Fin n)) [DecidableRel G.Adj] (H : Finset (Sym2 (Fin n))) (hcard : H.card < G.edgeFinset.card) (hcomp : 0 < compatible_labelings G H) (e : Sym2 (Fin n)) : (if e ∉ H ∧ 0 < compatible_labelings G (insert e H) then edge_arrival_prob G H e else 0) = if e ∉ H then (compatible_labelings G (insert e H) : ℝ) / ((G.edgeFinset.card - H.card : ℝ) * (compatible_labelings G H : ℝ)) else 0 := by have hd : ((G.edgeFinset.card - H.card : ℝ) * (compatible_labelings G H : ℝ)) ≠ 0 := by have h1 : (G.edgeFinset.card - H.card : ℝ) ≠ 0 := by have : (H.card : ℝ) < G.edgeFinset.card := Nat.cast_lt.mpr hcard linarith have h2 : (compatible_labelings G H : ℝ) ≠ 0 := by have : 0 < (compatible_labelings G H : ℝ) := Nat.cast_pos.mpr hcomp linarith exact mul_ne_zero h1 h2 unfold edge_arrival_prob rw [if_neg hd] by_cases he : e ∈ H · rw [if_neg (fun h => h.1 he), if_neg (fun h => h he)] · rw [if_pos he] by_cases hc : 0 < compatible_labelings G (insert e H) · rw [if_pos ⟨he, hc⟩] · rw [if_neg (fun h => hc h.2)] have : compatible_labelings G (insert e H) = 0 := by omega rw [this, Nat.cast_zero, zero_div]/-- Edge arrival transition probabilities sum to 1 over remaining edges. -/theorem edge_arrival_prob_sum {n : ℕ} (G : SimpleGraph (Fin n)) [DecidableRel G.Adj] (H : Finset (Sym2 (Fin n))) (hcard : H.card < G.edgeFinset.card) (hcomp : 0 < compatible_labelings G H) : ∑ e ∈ (Finset.univ : Finset (Sym2 (Fin n))), (if e ∉ H ∧ 0 < compatible_labelings G (insert e H) then edge_arrival_prob G H e else 0) = 1 := by have hd : ((G.edgeFinset.card - H.card : ℝ) * (compatible_labelings G H : ℝ)) ≠ 0 := by have h1 : (G.edgeFinset.card - H.card : ℝ) ≠ 0 := by have : (H.card : ℝ) < G.edgeFinset.card := Nat.cast_lt.mpr hcard linarith have h2 : (compatible_labelings G H : ℝ) ≠ 0 := by have : 0 < (compatible_labelings G H : ℝ) := Nat.cast_pos.mpr hcomp linarith exact mul_ne_zero h1 h2 simp_rw [edge_arrival_prob_sum_summand_eq G H hcard hcomp] rw [← Finset.sum_filter, ← Finset.sum_div, ← Nat.cast_sum] rw [edge_arrival_prob_sum_compatible_labelings_insert G H] push_cast rw [Nat.cast_sub (le_of_lt hcard)] exact div_self hd