AFTD Auto-Formalizing Theoretical Domains

cubic_half_integral_saturated_edges_min

def

For a finite simple graph G with decidable equality and adjacency, and an orientation o of G, the invariant b(G) is the infimum in the natural numbers of the number of edges e with |j(e)| = 1 among all half-integral stationary currents j on G.edgeFinset with sum of |j(e)| equal to the number of vertices.

Statement

noncomputable def cubic_half_integral_saturated_edges_min {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] (o : SimpleGraphOrientation G) : ℕ
Defined in
arXiv:2204.00875
Verified
12 Nov 2026
Axioms
none listed
Built on 3
  • is_stationary_currentA current j on the edges of an oriented finite simple graph G is stationary if at every vertex, the sum of currents leaving the vertex…
  • is_half_integral_currentFor a finite simple graph G with decidable equality on vertices and decidable adjacency, a function j on the edge finset of G into the…
  • SimpleGraphOrientationAn orientation of a finite simple graph G assigns to each edge an ordered pair of its endpoints.

Read back from the Lean

Given a finite type V with decidable equality, a simple graph G on V with decidable adjacency, and an orientation o of G (assigning to each edge an ordered pair of vertices forming that edge): cubic_half_integral_saturated_edges_min G o is defined as the infimum in ℕ (minimum if non-empty, 0 if empty) of the set of counts ∑_{e ∈ G.edgeFinset} (if |j(e)| = 1 then 1 else 0) over all functions j : G.edgeFinset → ℝ such that: 1. j is a stationary current with respect to o: for every vertex v ∈ V, the net flow out of v minus the net flow into v is 0, 2. j is half-integral: for every edge e ∈ G.edgeFinset, j(e) ∈ {0, 1/2, -1/2, 1, -1}, and 3. the sum of absolute values of j across all edges equals the number of vertices in V (∑_{e ∈ G.edgeFinset} |j(e)| = Fintype.card V).

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

/-- Minimum number b(G) of saturated edges among half-integral stationary currents with total current n. -/
noncomputable def cubic_half_integral_saturated_edges_min {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] (o : SimpleGraphOrientation G) : ℕ := sInf { (∑ e : G.edgeFinset, if |j e| = 1 then (1 : ℕ) else 0) |
    (j : G.edgeFinset → ℝ) (_ : is_stationary_current G o j)
    (_ : is_half_integral_current G j)
    (_ : ∑ e : G.edgeFinset, |j e| = Fintype.card V) }
See it in the graphDiscuss this resultChallenge it