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