dominating_occupancy_one_eq_avg_dominating_order_div_card
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.
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`).
uses
one_pow,mul_one,Finset.sum_const,nsmul_eq_mulrw [dominating_occupancy, simple_graph_avg_dominating_order, dominating_partition_function] simp only [one_pow, mul_one, Finset.sum_const, nsmul_eq_mul]
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.
uses
div_divpush_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).
- The average dominating set order `simple_graph_avg_dominating_order` is defined with values in ℚ, whereas the dominating occupancy takes values in ℝ. Line 8 (`push_cast`) is a formal coercion step to reconcile ℚ and ℝ that has no counterpart on paper.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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