dominating_average_stability_constant_lower_bound
Any multiplicative stability coefficient valid on the five-vertex path is at least51/5. This is a necessary constant, not the universal stability inequality.
Statement
theorem dominating_average_stability_constant_lower_bound (C : ℚ) :
letI := dominating_average_stability_path_five_decidable
(simple_graph_star_like_deletion_number (SimpleGraph.pathGraph 5) : ℚ) ≤
C * (2 * (Fintype.card (Fin 5) : ℚ) / 3 -
simple_graph_avg_dominating_order (SimpleGraph.pathGraph 5)) → 51/5 ≤ C- Source
- Finite sharpness certificate for the original OP-544 / IN-263 stability question. arXiv:2208.10475v2 Theorem2.9 supplies the extremal background. This formalizes the already computationally observed P5 obstruction to a smaller coefficient, not a proof of the universal bound or a research advance.
- Verified
- 27 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- 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…
- simple_graph_star_like_deletion_numberThe star-like deletion number d_*(G) of a finite simple graph G is the minimum cardinality of a subset X of vertices such that the induced…
- dominating_average_stability_path_five_decidableAn explicit computable adjacency decision for the five-vertex path.
- dominating_average_stability_path_five_meanThe five-vertex path has average dominating-set size55/17.
- dominating_average_stability_path_five_deletionThe minimum star-like vertex deletion distance of the five-vertex path is exactly1.
The proof, explained
The theorem establishes a necessary lower bound on the stability constant by evaluating the candidate inequality on a single counterexample graph: the 5-vertex path graph P₅. For this graph, the star-like deletion number is 1, the number of vertices is 5, and the average dominating set order is 55/17. Substituting these explicit quantities into the stability inequality reduces it to 1 ≤ C * (5/51), which immediately forces C ≥ 51/5.
The stability condition on the 5-vertex path graph simplifies to the requirement that 1 ≤ C * (5 / 51).
After providing the decidability of adjacency on the 5-vertex path graph, we rewrite the star-like deletion number of the path graph as 1 using dominating_average_stability_path_five_deletion and its average dominating set order as 55/17 using dominating_average_stability_path_five_mean. Numerical normalization then evaluates the vertex count as 5 and computes the rational expression 2 * 5 / 3 - 55 / 17 = 5 / 51.
uses
dominating_average_stability_path_five_deletion,dominating_average_stability_path_five_meanletI := dominating_average_stability_path_five_decidable rw [dominating_average_stability_path_five_deletion, dominating_average_stability_path_five_mean] norm_num
The stability constant C satisfies 51/5 ≤ C.
Assume the simplified hypothesis 1 ≤ C * (5 / 51). Multiplying both sides by 51/5 yields 51/5 ≤ C, which linear rational arithmetic confirms to complete the proof.
intro h linarith
dominating_average_stability_path_five_deletion- The star-like deletion number of the 5-vertex path graph is 1.
dominating_average_stability_path_five_mean- The average cardinality of a dominating set in the 5-vertex path graph is 55/17.
- Line 9 registers decidability of adjacency on the 5-vertex path graph, a formal typeclass requirement for computing the graph invariants 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.
set_option maxRecDepth 10000set_option maxHeartbeats 1000000theorem dominating_average_stability_constant_lower_bound (C : ℚ) : letI := dominating_average_stability_path_five_decidable (simple_graph_star_like_deletion_number (SimpleGraph.pathGraph 5) : ℚ) ≤ C * (2 * (Fintype.card (Fin 5) : ℚ) / 3 - simple_graph_avg_dominating_order (SimpleGraph.pathGraph 5)) → 51/5 ≤ C := by letI := dominating_average_stability_path_five_decidable rw [dominating_average_stability_path_five_deletion, dominating_average_stability_path_five_mean] norm_num intro h linarith