Active vertices of a residual graph
DefinitionFairReplay_Supplement_activeVerticesfairness-testinginformation-theoryp2o-gran-per-chapterp2o-plan-paperp2o-v1sequential-testing
For a residual fairness graph on finitely many vertices, the set of active vertices is
the vertices incident to at least one residual edge. Its size counts the inputs that a full suite-replay round must execute.
Formalization Note is a simple graph on with decidable adjacency.
Definition code
import Mathlib
namespace FairReplay.Supplement
/-- **Active vertices of a residual graph** `V+(H) = {v : deg_H(v) > 0}` (Sah, Zhang, Lian, *Testing
Fairness of Evolving Software under Uncertainty*, STOC 2027 submission, manuscript of 2026-11-03,
sha256 e23940a0…, §10 "Observation primitives", p.11 (PDF p.13): "Write V+(H) = {v : degH(v) > 0}";
§3, p.3: "Write V+(H) for vertices incident to a residual edge").
`activeVertices H` is the finite set of vertices of the simple graph `H` on `Fin n` that are incident
to at least one edge of `H`.
**Formalization Note** The residual graph is a `SimpleGraph` on the finite vertex type `Fin n`
(undirected, loopless), with decidable adjacency so that degrees are computable. -/
def activeVertices {n : ℕ} (H : SimpleGraph (Fin n)) [DecidableRel H.Adj] : Finset (Fin n) :=
Finset.univ.filter (fun v => 0 < H.degree v)
end FairReplay.Supplement
Source
Sah, Zhang, Lian, Testing Fairness of Evolving Software under Uncertainty, STOC 2027 submission (manuscript of 2026-11-03, sha256 e23940a0a0f5960aedaf6aba60adc41e966efc604b6379b3180b06590610d025), §10 "Observation primitives", p.11 (PDF p.13); §3, p.3 (PDF p.5)