Locally definable construction sequences from chains

Lax185574.ChainConstructionSequences · concepts/Lax185574/ChainConstructionSequences.lean · lax-185574

proven

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.

    Natural Language Statement

    Lemma

    For every n-vertex graph G and its chain of length ℓ there is a construction sequence G₁, …, G_λ of G such that the following properties hold for all r ≥ 1. Let k_r denote the radius-(5r+1) width of the chain and w_r ≔ k_r · π_G(k_r).

    1. The resulting construction sequence has radius-r width at most w_r and length λ ≤ O(n w₁).
    2. For every t ∈ [λ−1] and v ∈ V(G), the induced partial graph G_t[Ball^{G_{t+1}}_r(v)] is definable in some expansion of G with 2ℓ+1 unary predicates, using formulas of quantifier rank 7 with w_r parameters.
    3. The construction sequence can be computed in time O(ℓ n³), given G and its chain.
    Concept map
    22 concepts
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A
    Evidence

    In the paper

    • page 31 of this submission's paper

    Lean source view on GitHub

    1import Lax185574.Chains
    2import Lax185574.VCDimension
    3import Lax185574.ConstructionWidth
    4import Lax185574.LocalDefinability
    5import Lax185574.ConstructionSequences
    6import Lax185574.Algorithms
    7
    8/-!
    9---
    10title: Locally definable construction sequences from chains
    11type: lemma
    12---
    13For every n-vertex graph G and its chain of length ℓ there is a
    14construction sequence G₁, …, G_λ of G such that the following properties
    15hold for all r ≥ 1. Let k_r denote the radius-(5r+1) width of the chain
    16and w_r ≔ k_r · π_G(k_r).
    17
    181. The resulting construction sequence has radius-r width at most w_r
    19 and length λ ≤ O(n w₁).
    202. For every t ∈ [λ−1] and v ∈ V(G), the induced partial graph
    21 G_t[Ball^{G_{t+1}}_r(v)] is definable in some expansion of G with
    22 2ℓ+1 unary predicates, using formulas of quantifier rank 7 with w_r
    23 parameters.
    243. The construction sequence can be computed in time O(ℓ n³), given G
    25 and its chain.
    26
    27# Formalization notes
    28
    29The construction sequence is produced by a function `script` of the
    30graph and the chain, as a script of `Lax185574.ConstructionSequences`,
    31and the algorithm `A` computes this function, in the sense of
    32`Lax185574.Algorithms`. The algorithm, the constant `c` of the time
    33bound O((ℓ+1) · (n+1)³) and the constant `K` of the length bound come
    34first, so both constants are absolute. The input is the pair (G, S),
    35with the encodings of `Lax185574.Encodings`. A graph has the vertices
    36`Fin n`, and the notions of chains and construction sequences are
    37applied to its `SimpleGraph`.
    38
    39The width of item 1 is the radius-r width of
    40`Lax185574.ConstructionWidth`, which counts parts. The length bound
    41O(n w₁) is spelled out as K · (n+1) · (w₁+1). The number w_r is
    42`chainBound G S r`, with π_G the neighborhood complexity
    43`VCDimension.neighborhoodComplexity`. Item 2 is
    44`LocalDefinability.IsRadiusDefinable` with 2ℓ+1 predicates, w_r
    45parameters and rank 7.
    46
    47Every number in the encoding of the script is at most the length of the
    48encoding plus n (`Script.HasSmallNumbers`). The paper does not say
    49this. An algorithm can ensure it by giving the vertices of the initial
    50partial graph the colors 0, …, n − 1. The bound is what
    51`Lax185574.DefinableSequences` asks of its output.
    52-/
    53
    54namespace Lax185574.ChainConstructionSequences
    55
    56open Lax185574.Graphs Lax185574.Algorithms
    57open Lax185574.Chains Lax185574.VCDimension
    58open Lax185574.ConstructionSequences Lax185574.ConstructionWidth
    59open Lax185574.LocalDefinability
    60
    61universe z
    62
    63/-- The number `w_r = k_r · π_G(k_r)`, where `k_r` is the
    64radius-`(5r+1)` width of the chain `S`. -/
    65noncomputable def chainBound {V : Type z} (G : SimpleGraph V) (S : List (Finset V)) (r : ℕ) : ℕ :=
    66 chainWidth G (5 * r + 1) S * neighborhoodComplexity G (chainWidth G (5 * r + 1) S)
    67
    68/-- **Construction sequences from chains.** One algorithm computes, from
    69a graph and a chain of length `ℓ`, a construction sequence of the graph,
    70given by its script, in time `O((ℓ+1) · (n+1)³)`. For every `r ≥ 1`, it
    71has radius-`r` width at most `w_r` and length at most
    72`K · (n+1) · (w₁+1)`, and it is radius-`r` definable with `2ℓ+1`
    73predicates, `w_r` parameters and rank `7`. -/
    74axiom exists_constructionSequence_of_chain :
    75 ∃ (A : Algorithm) (c K : ℕ) (script : (G : Graph) → List (Finset (Fin G.n)) → Script G.n),
    76 ∀ (G : Graph) (S : List (Finset (Fin G.n))), IsChain S →
    77 let σ := script G S
    78 IsConstructionSequence G.toSimpleGraph σ.run ∧ σ.HasSmallNumbers ∧
    79 σ.run.length ≤ K * (G.n + 1) * (chainBound G.toSimpleGraph S 1 + 1) ∧
    80 (∀ r : ℕ, 1 ≤ r →
    81 constructionWidth r σ.run ≤ chainBound G.toSimpleGraph S r ∧
    82 IsRadiusDefinable G.toSimpleGraph σ.run r (2 * S.length + 1)
    83 (chainBound G.toSimpleGraph S r) 7) ∧
    84 A.Computes c (G, S) σ ((S.length + 1) * (G.n + 1) ^ 3)
    85
    86end Lax185574.ChainConstructionSequences
    87
    Show Proof
    Formalization notes

    The construction sequence is produced by a function scriptscript of the graph and the chain, as a script of Lax185574.ConstructionSequencesLax185574.ConstructionSequences, and the algorithm AA computes this function, in the sense of Lax185574.AlgorithmsLax185574.Algorithms. The algorithm, the constant cc of the time bound O((ℓ+1) · (n+1)³) and the constant KK of the length bound come first, so both constants are absolute. The input is the pair (G, S), with the encodings of Lax185574.EncodingsLax185574.Encodings. A graph has the vertices FinnFin n, and the notions of chains and construction sequences are applied to its SimpleGraphSimpleGraph.

    The width of item 1 is the radius-r width of Lax185574.ConstructionWidthLax185574.ConstructionWidth, which counts parts. The length bound O(n w₁) is spelled out as K · (n+1) · (w₁+1). The number w_r is chainBoundGSrchainBound G S r, with π_G the neighborhood complexity VCDimension.neighborhoodComplexityVCDimension.neighborhoodComplexity. Item 2 is LocalDefinability.IsRadiusDefinableLocalDefinability.IsRadiusDefinable with 2ℓ+1 predicates, w_r parameters and rank 7.

    Every number in the encoding of the script is at most the length of the encoding plus n (Script.HasSmallNumbersScript.HasSmallNumbers). The paper does not say this. An algorithm can ensure it by giving the vertices of the initial partial graph the colors 0, …, n − 1. The bound is what Lax185574.DefinableSequencesLax185574.DefinableSequences asks of its output.

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…