AFTD Auto-Formalizing Theoretical Domains

is_det_extremal

def

A finite graph G is det-extremal if it admits an equitable bipartition into parts of equal size n such that the absolute value of the determinant of its biadjacency matrix equals the permanent.

Statement

def is_det_extremal {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] : Prop
Defined in
arXiv:2611.16649 Sec. 1, p. 2
Verified
13 Nov 2026
Axioms
none listed

Read back from the Lean

Given a finite type V with decidable equality and a simple graph G on V with decidable adjacency, is_det_extremal G asserts that there exist a natural number n and two functions f, g : Fin n → V such that: 1. f is injective; 2. g is injective; 3. The ranges of f and g are disjoint; 4. The union of the ranges of f and g is all of V (together with (1)–(3), this means f and g partition V into two parts of equal size n); 5. For all i, j : Fin n, f i and f j are not adjacent in G (the range of f is an independent set); 6. For all i, j : Fin n, g i and g j are not adjacent in G (the range of g is an independent set); 7. The absolute value of the determinant of the n × n integer matrix A (defined by A i j = 1 if G.Adj (f i) (g j) and 0 otherwise) is equal to the permanent of A.

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

/-- A finite bipartite graph is det-extremal if its biadjacency matrix has |det B| = per B. -/
def is_det_extremal {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] : Prop := ∃ (n : ℕ) (f g : Fin n → V),
    Function.Injective f ∧ Function.Injective g ∧
    Disjoint (Set.range f) (Set.range g) ∧
    (Set.range f ∪ Set.range g = Set.univ) ∧
    (∀ i j, ¬ G.Adj (f i) (f j)) ∧ (∀ i j, ¬ G.Adj (g i) (g j)) ∧
    |Matrix.det (fun i j => if G.Adj (f i) (g j) then (1 : ℤ) else 0)| =
      Matrix.permanent (fun i j => if G.Adj (f i) (g j) then (1 : ℤ) else 0)
See it in the graphDiscuss this resultChallenge it