AFTD Auto-Formalizing Theoretical Domains

compatible_labelings

def

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
See it in the graphDiscuss this resultChallenge it