AFTD Auto-Formalizing Theoretical Domains

edge_arrival_prob

def

For 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 : Sym2 (Fin n), edge_arrival_prob G H e is defined as (compatible_labelings G (insert e H) : ℝ) / ((G.edgeFinset.card - H.card : ℝ) * (compatible_labelings G H : ℝ)) if the denominator is nonzero, and 0 otherwise.

Statement

noncomputable def edge_arrival_prob {n : ℕ} (G : SimpleGraph (Fin n)) [DecidableRel G.Adj]
    (H : Finset (Sym2 (Fin n))) (e : Sym2 (Fin n)) : ℝ
Defined in
arXiv:2611.13571, Section 5.1, Equation (13)
Verified
12 Nov 2026
Axioms
none listed
Built on 1
  • 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))),…
Used by 5
  • bellman_valueFor a simple graph G on vertex set Fin n with decidable adjacency, an observed edge set H : Finset (Sym2 (Fin n)), and an unmatched vertex…
  • online_matching_policy_value_le_bellmanFor a simple graph G on vertex set Fin n with decidable adjacency, every online matching policy pol : OnlineMatchingPolicy n satisfies…
  • edge_arrival_prob_sumFor 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 <…
  • policy_valueFor a simple graph G on vertex set Fin n with decidable adjacency, an online matching policy pol : OnlineMatchingPolicy n, an observed…
  • optimal_online_matching_policy_achieves_valueFor a simple graph G on vertex set Fin n with decidable adjacency, the optimal online matching policy optimal_online_policy G achieves…

Read back from the Lean

A definition edge_arrival_prob that, given: - a natural number n (implicit), - a simple graph G on the vertex set Fin n, - a decidable adjacency relation on G ([DecidableRel G.Adj]), - a finite set of unordered vertex pairs H : Finset (Sym2 (Fin n)), and - an unordered vertex pair e : Sym2 (Fin n), computes a real number defined by cases: - If (G.edgeFinset.card - H.card : ℝ) * (compatible_labelings G H : ℝ) = 0, it returns 0. (Here, compatible_labelings G H is the number of permutations π : Equiv.Perm (Fin n) such that H is a subset of the edge set of G.map π.toEmbedding, and G.edgeFinset.card - H.card is natural subtraction coerced to ℝ.) - Otherwise, it returns: compatible_labelings G (insert e H) / ((G.edgeFinset.card - H.card) * compatible_labelings G H) (all quantities coerced to ℝ).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- The transition probability p(e | H) that edge e arrives next given observed edges H. -/
noncomputable def edge_arrival_prob {n : ℕ} (G : SimpleGraph (Fin n)) [DecidableRel G.Adj]
    (H : Finset (Sym2 (Fin n))) (e : Sym2 (Fin n)) : ℝ :=
  if (G.edgeFinset.card - H.card : ℝ) * (compatible_labelings G H : ℝ) = 0 then 0
  else (compatible_labelings G (insert e H) : ℝ) /
    ((G.edgeFinset.card - H.card : ℝ) * (compatible_labelings G H : ℝ))
See it in the graphDiscuss this resultChallenge it