Algorithm D stops within log(n²)/log(18/17) + 16 ≤ 25·log n + 16 rounds with a maximal independent set
ProvedLubyMIS.Derandomized.algorithmD_roundsLet be a graph on the vertices and let be a prime with . Every run of Algorithm D terminates: there is a such that the vertex set of the current graph is nonempty before each of the first executions of the loop body and empty after the -th, so the loop body is executed exactly times. Moreover
and the output set is a maximal independent set of .
This is the deterministic guarantee of Algorithm D: a maximal independent set is found in parallel rounds without random bits, for every choice of maximizing vertex in Case 1 and every choice of maximizing sample point in Case 2.
Formalization Note The ratio does not depend on the base of the logarithm; is base 2, following the paper's convention that all logarithms are base 2. The statement holds for every run, that is, for every tie-break among vertices of maximum degree and every maximizing sample point. The P-RAM processor count and running time are not part of the statement. For no prime exists and the statement is vacuous; for the bound is .
import Mathlib import Definitions.Def_LubyMIS_Derandomized_Basic import Definitions.Def_LubyMIS_Derandomized_AlgorithmD
namespace LubyMIS.Derandomized
/-- Algorithm D (Luby 1986, §4.4, p. 1047, with §3.1, p. 1039): for every graph `G` on `n` vertices
and every prime `n ≤ q ≤ 2n`, every run of Algorithm D stops after `k` executions of the loop body
with `k ≤ log(n²)/log(18/17) + 16 ≤ 25·log₂ n + 16`, and the set `I` it outputs is a maximal
independent set of `G`. -/
theorem algorithmD_rounds (n : ℕ) (G : SimpleGraph (Fin n)) [DecidableRel G.Adj] (q : ℕ)
(hq : q.Prime) (hnq : n ≤ q) (hq2 : q ≤ 2 * n) (s : ℕ → Finset (Fin n) × Finset (Fin n))
(hs : IsRun G q s) :
∃ k : ℕ, (s k).2 = ∅ ∧ (∀ j < k, (s j).2.Nonempty) ∧
(k : ℝ) ≤ Real.log ((n : ℝ) ^ 2) / Real.log (18 / 17) + 16 ∧
(k : ℝ) ≤ 25 * Real.logb 2 (n : ℝ) + 16 ∧
Maximal G.IsIndepSet ((s k).1 : Set (Fin n)) := by sorry
end LubyMIS.Derandomized
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Throughout, is a natural number and is a simple graph (undirected, no loops, no multiple edges) on the vertex set . 's adjacency relation is assumed decidable. This is a computability requirement only and places no mathematical restriction on . The statement also takes:
- a natural number ;
- a sequence . For each index , is a pair of finite subsets of . Below, is called the first component and the second component.
Hypotheses.
- is prime.
- .
- .
- holds. This is a predicate on the graph, the number and the whole sequence . It is defined in an imported file whose code is not part of this declaration, so this read-back cannot say what it requires. In particular, it cannot say how is related to , what is, or whether the predicate can be satisfied at all. Every claim below holds only for sequences that satisfy it.
Conclusion. There exists a natural number with all of the following properties:
- The second component is empty at step : .
- is the first such index: for every .
- First bound on (natural logarithm):
- Second bound on (base-2 logarithm):
The two bounds are asserted separately; neither is derived from the other within the statement.
-
Maximal independent set: the first component is a maximal independent set of . That is:
- no two distinct vertices of are adjacent in ; and
- every independent set with satisfies .
"Maximal" here means maximal with respect to inclusion, not of maximum size.
The statement says nothing about for . It also says nothing about for beyond what may impose.
Degenerate cases.
- : hypotheses 2 and 3 force , which is not prime. The hypotheses cannot all hold, so the statement is vacuously true and asserts nothing.
- : the hypotheses force . Both bounds become , because and . The only maximal independent set of the one-vertex loopless graph is , so the conclusion requires .
- in general: and , so neither logarithm is evaluated at or at a negative number. The denominator is a fixed positive number. No default values of total functions arise in the bounds.
- Whether the statement says anything at all: a prime with exists for every . So whether the theorem has any non-vacuous instance depends entirely on whether can be satisfied, and that cannot be determined from the code shown.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.