edge_arrival_prob
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 : ℝ))