AFTD Auto-Formalizing Theoretical Domains

has_mad_lt

def

Given a finite type V with decidable equality, a simple graph G on V with decidable adjacency, and a rational number q, has_mad_lt G q asserts that for every nonempty finite subset s of V, twice the number of edges in the induced subgraph of G on s divided by the cardinality of s (evaluated in ℚ) is strictly less than q.

Statement

def has_mad_lt {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] (q : ℚ) : Prop
Defined in
arXiv:2610.34874
Verified
27 Oct 2026
Axioms
none listed
Used by 1

Read back from the Lean

For a finite type V with decidable equality, a simple graph G on V with decidable adjacency, and a rational number q, has_mad_lt G q asserts that for every nonempty finite subset s of V, twice the number of edges in the induced subgraph of G on s, divided by the cardinality of s (computed in ℚ), is strictly less than q. That is, the average degree of every nonempty induced subgraph of G is strictly less than q.

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 maximum average degree of G is strictly less than a rational number q. -/
def has_mad_lt {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] (q : ℚ) : Prop := ∀ (s : Finset V) (_ : s.Nonempty),
    2 * ((G.induce (s : Set V)).edgeFinset.card : ℚ) / (s.card : ℚ) < q
See it in the graphDiscuss this resultChallenge it