Finite-label success, average query complexity and MIS
DefinitionGreedyColoringLCA969_LowerBound_Supplement_LabelPerformanceFix a labeling problem , a coding , a standard-oracle LCA and a represented graph . Global success on a shared random tape means there is a correct labeling such that every execution at terminates with return code :
The probability uses the published independent fair-bit tape law. Error-free on degree bound means this probability is one for every size and every representation of a graph of maximum degree at most . For an arbitrary finite label set a fixed bijection codes its labels by ; Boolean labels use , . An out-of-range code and a nonterminating answer both fail global success.
Average query complexity is , with value zero on the empty graph. Each expectation remains a nonnegative extended real; it is not replaced by a real integral on nonintegrable costs. The MIS predicate requires the vertices labeled to be independent and every vertex labeled to have a neighbor labeled . Regularity means every vertex has exactly neighbors. These concepts share the published execution and query costs without imposing correctness or resource bounds on algorithms.
The general set predicate for maximal independence is reused from the published SmoothedMIS.IsMIS; this item only turns it into a Boolean-labeling problem by taking the set of vertices labeled . The imported body adds no graph assumptions.
import Definitions.Def_GreedyColoringLCA969_LowerBound_Supplement_Labeling
import Definitions.Def_GreedyColoringLCA969_LowerBound_Performance
import Definitions.Def_SmoothedMIS_IsMIS
open scoped ENNReal BigOperators
open MeasureTheory Classical
set_option autoImplicit false
namespace GreedyColoringLCA969.LowerBound.Supplement
/-- A fixed bijection from finite labels to codes 1,...,|L|. -/
noncomputable def finiteCode (L : Type) [Fintype L] (α : L) : ℕ+ :=
⟨(Fintype.equivFin L α).val + 1, Nat.succ_pos _⟩
def boolCode : Bool → ℕ+
| false => 1
| true => 2
/-- Global correctness, using the actual published execution on one shared tape.
An invalid code or a nonterminating answer makes the tape unsuccessful. -/
def labelingSuccess {L : Type} (P : LabelProblem L) (code : L → ℕ+)
{n : ℕ} (A : Algorithm .standard) (R : Representation n) : Set Tape :=
{r | ∃ l : Fin n → L, P R.graph l ∧ ∀ v, Returns A R r v (code (l v))}
noncomputable def labelingProbability {L : Type} (P : LabelProblem L) (code : L → ℕ+)
{n : ℕ} (A : Algorithm .standard) (R : Representation n) : ℝ≥0∞ :=
tapeLaw (labelingSuccess P code A R)
def ErrorFreeOn {L : Type} (P : LabelProblem L) (code : L → ℕ+)
(A : Algorithm .standard) (Δ : ℕ) : Prop :=
∀ (n : ℕ) (R : Representation n), MaxDegreeAtMost R.graph Δ →
labelingProbability P code A R = 1
noncomputable def averageQueries {n : ℕ} (A : Algorithm .standard)
(R : Representation n) : ℝ≥0∞ :=
if n = 0 then 0 else (∑ v, expectedQueries A R v) / (n : ℝ≥0∞)
/-- Independence and domination, not maximum cardinality. -/
def MIS : LabelProblem Bool := fun G l =>
SmoothedMIS.IsMIS G {v | l v = true}
def Regular {n : ℕ} (G : SimpleGraph (Fin n)) (Δ : ℕ) : Prop :=
∀ v, Nat.card {u // G.Adj v u} = Δ
end GreedyColoringLCA969.LowerBound.Supplement