binary_function_graph
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
- binary_function_graph_adj_constIn the binary function graph of any simple graph on a nonempty vertex set, the constant false and constant true functions are adjacent.
- binary_function_graph_clique_free_threeIf a simple graph G has chromatic number strictly greater than 6, then its binary function graph is triangle-free (3-clique free).
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⟩