compatible_labelings
For 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))), compatible_labelings G H is the number of permutations π : Equiv.Perm (Fin n) such that H is a subset of (G.map π.toEmbedding).edgeFinset.
Statement
def compatible_labelings {n : ℕ} (G : SimpleGraph (Fin n)) [DecidableRel G.Adj]
(H : Finset (Sym2 (Fin n))) : ℕ- Defined in
- arXiv:2611.13571, Section 5.1
- Verified
- 12 Nov 2026
- Axioms
- none listed
- Used by 7
- edge_arrival_probFor 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…
- compatible_labelings_emptyFor any simple graph G on vertex set Fin n with decidable adjacency, compatible_labelings G ∅ = Nat.factorial n.
- 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
Given an implicit natural number n, a simple graph G on the vertex type Fin n (with decidable adjacency), and a finite set H of unordered pairs of vertices in Fin n (elements of Sym2 (Fin n)), compatible_labelings G H is defined as the number of permutations π of Fin n such that H is a subset of the edge finset of the graph obtained by mapping G along π (as an embedding).
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 number of vertex labelings compatible with the observed edges H. -/ def compatible_labelings {n : ℕ} (G : SimpleGraph (Fin n)) [DecidableRel G.Adj] (H : Finset (Sym2 (Fin n))) : ℕ := (Finset.univ.filter (fun π : Equiv.Perm (Fin n) => H ⊆ (G.map π.toEmbedding).edgeFinset)).card