AFTD Auto-Formalizing Theoretical Domains

binary_function_graph

def

The binary function graph of a simple graph G is the graph with vertices V → Bool, where two distinct functions f and g are adjacent if and only if for each boolean value b, the set of vertices where both functions evaluate to b is an independent set in G.

Statement

def binary_function_graph {V : Type*} (G : SimpleGraph V) : SimpleGraph (V → Bool)
Defined in
arXiv:2610.37920 Section 2
Verified
01 Nov 2026
Axioms
none listed
Used by 2

Read back from the Lean

Given a type V and a simple graph G on V, binary_function_graph G is the simple graph on the vertex type V → Bool in which two functions f, g : V → Bool are adjacent if and only if f ≠ g and, for every b : Bool, the preimage intersection {v : V | f v = b ∧ g v = b} is an independent set in G (i.e., no two distinct vertices in V on which both f and g take value b are adjacent in G).

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 binary function graph of a simple graph G, whose vertices are binary functions on V(G). -/
def binary_function_graph {V : Type*} (G : SimpleGraph V) : SimpleGraph (V → Bool) where
  Adj f g := f ≠ g ∧ ∀ b : Bool, G.IsIndepSet {v | f v = b ∧ g v = b}
  symm := ⟨fun f g ⟨hne, hind⟩ => ⟨hne.symm, fun b => by simpa [and_comm] using hind b⟩⟩
  loopless := ⟨fun f ⟨hne, _⟩ => hne rfl⟩
See it in the graphDiscuss this resultChallenge it