is_det_extremal
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)