AFTD Auto-Formalizing Theoretical Domains

dominating_occupancy_one_eq_avg_dominating_order_div_card

theoremverified

At activity lam = 1, the dominating occupancy equals the average dominating set order divided by the number of vertices.

Statement

open Classical in
theorem dominating_occupancy_one_eq_avg_dominating_order_div_card {V : Type*} [Fintype V]
    (G : SimpleGraph V) :
    dominating_occupancy G 1 = (simple_graph_avg_dominating_order G : ℝ) / Fintype.card V
Source
step towards weighted_dominating_occupancy_at_one_le_two_thirds
Verified
28 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • dominating_occupancyThe normalized lambda-biased dominating occupancy rho_G(lam) of a finite simple graph G on vertex set V is the sum over all dominating…
  • simple_graph_avg_dominating_orderavd(G): the global average order of dominating sets of G, i.e. the average size of all dominating sets of G. This is the quantity of…
  • dominating_partition_functionThe dominating set partition function Z_G(lam) of a finite simple graph G is the sum over all dominating sets S of G of lam^{|S|}.
  • simple_graph_dominating_setsD(G): the dominating sets of G, i.e. the finite vertex sets S such that every vertex of G lies in S or is adjacent to a vertex of S.

The proof, explained

The proof unfolds the definitions of dominating occupancy, the dominating partition function, and the average dominating set order. At activity λ = 1, the partition function simplifies to the total count of dominating sets, and the occupancy numerator simplifies to the sum of their sizes. Dividing the average dominating set order by |V| produces the same fraction, which completes the proof after simplifying the compound division and using commutativity of multiplication.

  1. At activity λ = 1, the dominating occupancy simplifies to (∑_{S ∈ D} |S|) / (|V| * |D|), where D is the set of dominating sets of G.

    We unfold the definitions of dominating occupancy, average dominating set order, and the dominating partition function. At activity λ = 1, each term 1^{|S|} simplifies to 1 (using `one_pow`), so |S| * 1^{|S|} becomes |S| (using `mul_one`). The partition function sum ∑_{S ∈ D} 1^{|S|} simplifies to the total number of dominating sets |D| (using `Finset.sum_const` and `nsmul_eq_mul`).

    lines 6–7

    uses one_pow, mul_one, Finset.sum_const, nsmul_eq_mul

      rw [dominating_occupancy, simple_graph_avg_dominating_order, dominating_partition_function]
      simp only [one_pow, mul_one, Finset.sum_const, nsmul_eq_mul]
  2. The simplified dominating occupancy equals the average dominating order divided by |V|.

    The average dominating order is defined in ℚ as (∑_{S ∈ D} |S|) / |D|. Using `push_cast`, the coercion from ℚ to ℝ distributes across the division, turning the right-hand side into ((∑_{S ∈ D} |S|) / |D|) / |V| in the reals. Rewriting with `div_div` transforms this compound fraction into (∑_{S ∈ D} |S|) / (|D| * |V|). Finally, `ring_nf` recognizes that |D| * |V| = |V| * |D| by commutativity of real multiplication, closing the goal.

    lines 8–10

    uses div_div

      push_cast
      rw [div_div]
      ring_nf
one_pow
Raising 1 to any natural power n equals 1 (1^n = 1).
mul_one
Multiplying an element by 1 on the right leaves it unchanged (a * 1 = a).
Finset.sum_const
Summing a constant value b over a finite set s equals the cardinality |s| multiplied by b.
nsmul_eq_mul
Natural-number scalar multiplication n • a equals multiplication by the cast of n (↑n * a).
div_div
Iterated division (a / b) / c equals division by the product a / (b * c).

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

open Classical in/-- At activity lam = 1, the dominating occupancy equals the average dominating set order divided by the number of vertices. -/theorem dominating_occupancy_one_eq_avg_dominating_order_div_card {V : Type*} [Fintype V]    (G : SimpleGraph V) :    dominating_occupancy G 1 = (simple_graph_avg_dominating_order G : ℝ) / Fintype.card V := by  rw [dominating_occupancy, simple_graph_avg_dominating_order, dominating_partition_function]  simp only [one_pow, mul_one, Finset.sum_const, nsmul_eq_mul]  push_cast  rw [div_div]  ring_nf
See it in the graphDiscuss this resultChallenge it