Draft — mutable and not usable as a dependency; its citation marks the draft state.

Lax3.NeighborhoodCovers

Sparse neighborhood covers

concepts/Lax3/NeighborhoodCovers.lean · lax-3

definition

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this concept may be incorrect.

No flags have been submitted.

    Community review

    Flag this concept

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    No source line selected.

    Concept map

    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A

    Definition

    An r-neighborhood cover of a graph is a family of vertex sets, the clusters, such that the r-ball of every vertex is contained in some cluster. Its radius is the largest radius of a cluster, and its degree is the largest number of clusters any one vertex belongs to. A cover is useful when its radius is not much larger than r and its degree is small: local computations can then be done inside single clusters, and the degree bounds how often each vertex pays for them.

    This is the notion of Grohe–Kreutzer–Siebertz §6 (radius 2r there, as here). It is the load distributor of the model-checking algorithm: the truth of a local formula at a vertex is decided inside a cluster containing the vertex's ball, and a degree of n^ε caps the total size of all clusters at n^(1+ε).

    Lean source view on GitHub

    1import Lax3.ColoredGraphs
    2import Mathlib.Data.Set.Card
    3
    4/-!
    5---
    6title: Sparse neighborhood covers
    7type: definition
    8---
    9An *r*-neighborhood cover of a graph is a family of vertex sets, the
    10clusters, such that the *r*-ball of every vertex is contained in some
    11cluster. Its radius is the largest radius of a cluster, and its degree
    12is the largest number of clusters any one vertex belongs to. A cover
    13is useful when its radius is not much larger than *r* and its degree
    14is small: local computations can then be done inside single clusters,
    15and the degree bounds how often each vertex pays for them.
    16
    17This is the notion of Grohe–Kreutzer–Siebertz §6 (radius 2*r* there,
    18as here). It is the load distributor of the model-checking algorithm:
    19the truth of a local formula at a vertex is decided inside a cluster
    20containing the vertex's ball, and a degree of *n*^ε caps the total
    21size of all clusters at *n*^(1+ε).
    22
    23# Formalization notes
    24
    25Clusters are indexed by vertices — `X : Fin n → Set (Fin n)`, cluster
    26`X u` centered at `u` — rather than given as a bare family of sets.
    27The ordering-based construction that discharges the existence theorem
    28produces exactly this shape (one cluster per vertex, some possibly
    29empty, `X u` inside the 2`r`-ball of `u`), the algorithm's
    30cover-assignment map "read the truth of a formula at `v` inside the
    31cluster of `f(v)`" needs the index to point at a center, and a bare
    32family is recovered as the image of the indexing if ever needed.
    33Centering also makes the radius condition self-witnessing: `X u` lies
    34in the ball *of its own index*, no existential center.
    35
    36The three fields quantify over all of `Fin n`, including vertices
    37outside every cluster of interest; an empty cluster satisfies both the
    38radius and the degree conditions vacuously, so this costs nothing.
    39Degree is stated with `Set.ncard`, the cardinality idiom of the Lax12
    40concepts this submission composes with.
    41-/
    42
    43namespace Lax3.NeighborhoodCovers
    44
    45open Lax3.ColoredGraphs
    46
    47/-- `X` is an `r`-neighborhood cover of `G` of radius `2r` and degree
    48`d`: every `r`-ball is inside some cluster, the cluster of `u` lies in
    49the `2r`-ball of `u`, and no vertex is in more than `d` clusters. -/
    50structure IsNeighborhoodCover {n : ℕ} (G : SimpleGraph (Fin n)) (r : ℕ)
    51 (X : Fin n → Set (Fin n)) (d : ℕ) : Prop where
    52 /-- Every `r`-ball is contained in some cluster. -/
    53 ball_subset : ∀ v : Fin n, ∃ u : Fin n, ball G r v ⊆ X u
    54 /-- Each cluster lies in the `2r`-ball of its center. -/
    55 subset_ball : ∀ u : Fin n, X u ⊆ ball G (2 * r) u
    56 /-- No vertex belongs to more than `d` clusters. -/
    57 degree_le : ∀ v : Fin n, {u : Fin n | v ∈ X u}.ncard ≤ d
    58
    59end Lax3.NeighborhoodCovers
    60

    Formalization notes

    Clusters are indexed by vertices — X:FinnSet(Finn)X : Fin n → Set (Fin n), cluster XuX u centered at uu — rather than given as a bare family of sets. The ordering-based construction that discharges the existence theorem produces exactly this shape (one cluster per vertex, some possibly empty, XuX u inside the 2rr-ball of uu), the algorithm's cover-assignment map "read the truth of a formula at vv inside the cluster of f(v)f(v)" needs the index to point at a center, and a bare family is recovered as the image of the indexing if ever needed. Centering also makes the radius condition self-witnessing: XuX u lies in the ball of its own index, no existential center.

    The three fields quantify over all of FinnFin n, including vertices outside every cluster of interest; an empty cluster satisfies both the radius and the degree conditions vacuously, so this costs nothing. Degree is stated with Set.ncardSet.ncard, the cardinality idiom of the Lax12 concepts this submission composes with.

    Community review

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above; your ORCID profile must share a public name.

    0 comments

    Loading discussion…