§3.3 — at most edges join to (and to )
ProvedDistVerif.Simulation.cut_edges_leLet be the network of §3.1 with its -left and -right sets , , and let be an integer with
Then at most edges of join a vertex of to a vertex of , and at most edges join a vertex of to a vertex of .
The paper states this observation in the sentence preceding Lemma 3.4, and identifies the edges in its proof: all edges linking vertices in and are of the form where is the leftmost level- tree vertex in and one of its children, for . The bound is what limits the information crossing from Alice's side to Bob's side in one round to messages, independently of the number of paths.
Formalization Note Edges are counted as ordered pairs with outside (resp. ) and (resp. ). Since , at most one orientation of an edge qualifies, so this is the number of edges. The hypotheses (so that is a genuine predecessor) and the strict inequality, written in , are those of Lemma 3.4.
import Mathlib import Definitions.Def_DistVerif_Simulation_Network
namespace DistVerif.Simulation
/-- **§3.3, sentence before Lemma 3.4** (p. 1249). For `0 < t < (d^p - 1)/2`, at most `d·p`
edges of `G(Γ, d, p)` join a vertex of `V \ R_{t-1}` to a vertex of `R_t`, and at most `d·p`
join a vertex of `V \ L_{t-1}` to a vertex of `L_t`. Edges are counted as ordered pairs
`(w, u)` with `w` outside and `u` inside; since `R_t ⊆ R_{t-1}` (and `L_t ⊆ L_{t-1}`), each
edge contributes at most one such pair. -/
theorem cut_edges_le (Γ d p t : ℕ) (ht0 : 0 < t) (ht : (t : ℝ) < ((d : ℝ) ^ p - 1) / 2) :
(Finset.univ.filter fun q : Vtx Γ d p × Vtx Γ d p =>
(graph Γ d p).Adj q.1 q.2 ∧ q.1 ∉ R Γ d p (t - 1) ∧ q.2 ∈ R Γ d p t).card ≤ d * p ∧
(Finset.univ.filter fun q : Vtx Γ d p × Vtx Γ d p =>
(graph Γ d p).Adj q.1 q.2 ∧ q.1 ∉ L Γ d p (t - 1) ∧ q.2 ∈ L Γ d p t).card ≤ d * p := by sorry
end DistVerif.Simulation
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.