Claim 4.3, p. 17 — a path visits k_n(γ)+1 vertices and k_n(γ)+k_r(γ) edges
ProvedSBMThreshold.Main.claim_4_3combinatoricsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1pathsstochastic-block-model
Let be a path (consecutive vertices distinct) and let and be its numbers of new and returning steps (Definition 4.1). Then
Every new step adds one vertex and one edge, a returning step adds one edge, and an old step adds neither. The claim converts the edge-type counts into the sizes of the path's vertex and edge sets, which is how the path counts of §4 are turned into powers of .
Preamble
import Mathlib import Definitions.Def_SBMThreshold_Main_Setting import Definitions.Def_SBMThreshold_Main_Paths open Filter Topology Finset
Formal statement
namespace SBMThreshold.Main
/-- Claim 4.3 (p. 17): a path visits `k_n(γ) + 1` vertices and `k_n(γ) + k_r(γ)` edges. -/
theorem claim_4_3 {n k : ℕ} (γ : Fin (k + 1) → Fin n) (hγ : IsPath γ) :
(pathVertices γ).card = kNew γ + 1 ∧ (pathEdges γ).card = kNew γ + kRet γ := by sorry
end SBMThreshold.Main
Source
Mossel, Neeman and Sly, A Proof of the Block Model Threshold Conjecture, arXiv:1311.4115v4, p. 17, Claim 4.3
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.