has_mad_lt
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
- has_mad_lt_exists_degree_le_twoIf has_mad_lt G (7/3) holds, then every nonempty finite vertex set s contains a vertex with at most 2 neighbours in s.
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