Locally definable construction sequences from chains
Lax185574.ChainConstructionSequences · concepts/Lax185574/ChainConstructionSequences.lean · lax-185574
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural 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).
- The resulting construction sequence has radius-r width at most w_r and length λ ≤ O(n w₁).
- 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.
- The construction sequence can be computed in time O(ℓ n³), given G and its chain.
Concept map
Evidence
Each proof establishes this claim relative to its assumptions.
In the paper
- page 31 of this submission's paper
Lean source view on GitHub
| 1 | import Lax185574.Chains |
| 2 | import Lax185574.VCDimension |
| 3 | import Lax185574.ConstructionWidth |
| 4 | import Lax185574.LocalDefinability |
| 5 | import Lax185574.ConstructionSequences |
| 6 | import Lax185574.Algorithms |
| 7 | |
| 8 | /-! |
| 9 | --- |
| 10 | title: Locally definable construction sequences from chains |
| 11 | type: lemma |
| 12 | --- |
| 13 | For every n-vertex graph G and its chain of length ℓ there is a |
| 14 | construction sequence G₁, …, G_λ of G such that the following properties |
| 15 | hold for all r ≥ 1. Let k_r denote the radius-(5r+1) width of the chain |
| 16 | and w_r ≔ k_r · π_G(k_r). |
| 17 | |
| 18 | 1. The resulting construction sequence has radius-r width at most w_r |
| 19 | and length λ ≤ O(n w₁). |
| 20 | 2. 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. |
| 24 | 3. The construction sequence can be computed in time O(ℓ n³), given G |
| 25 | and its chain. |
| 26 | |
| 27 | # Formalization notes |
| 28 | |
| 29 | The construction sequence is produced by a function `script` of the |
| 30 | graph and the chain, as a script of `Lax185574.ConstructionSequences`, |
| 31 | and the algorithm `A` computes this function, in the sense of |
| 32 | `Lax185574.Algorithms`. The algorithm, the constant `c` of the time |
| 33 | bound O((ℓ+1) · (n+1)³) and the constant `K` of the length bound come |
| 34 | first, so both constants are absolute. The input is the pair (G, S), |
| 35 | with the encodings of `Lax185574.Encodings`. A graph has the vertices |
| 36 | `Fin n`, and the notions of chains and construction sequences are |
| 37 | applied to its `SimpleGraph`. |
| 38 | |
| 39 | The width of item 1 is the radius-r width of |
| 40 | `Lax185574.ConstructionWidth`, which counts parts. The length bound |
| 41 | O(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 |
| 45 | parameters and rank 7. |
| 46 | |
| 47 | Every number in the encoding of the script is at most the length of the |
| 48 | encoding plus n (`Script.HasSmallNumbers`). The paper does not say |
| 49 | this. An algorithm can ensure it by giving the vertices of the initial |
| 50 | partial graph the colors 0, …, n − 1. The bound is what |
| 51 | `Lax185574.DefinableSequences` asks of its output. |
| 52 | -/ |
| 53 | |
| 54 | namespace Lax185574.ChainConstructionSequences |
| 55 | |
| 56 | open Lax185574.Graphs Lax185574.Algorithms |
| 57 | open Lax185574.Chains Lax185574.VCDimension |
| 58 | open Lax185574.ConstructionSequences Lax185574.ConstructionWidth |
| 59 | open Lax185574.LocalDefinability |
| 60 | |
| 61 | universe z |
| 62 | |
| 63 | /-- The number `w_r = k_r · π_G(k_r)`, where `k_r` is the |
| 64 | radius-`(5r+1)` width of the chain `S`. -/ |
| 65 | noncomputable 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 |
| 69 | a graph and a chain of length `ℓ`, a construction sequence of the graph, |
| 70 | given by its script, in time `O((ℓ+1) · (n+1)³)`. For every `r ≥ 1`, it |
| 71 | has 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` |
| 73 | predicates, `w_r` parameters and rank `7`. -/ |
| 74 | axiom 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 | |
| 86 | end Lax185574.ChainConstructionSequences |
| 87 |
Formalization notes
The construction sequence is produced by a function of the graph and the chain, as a script of , and the algorithm computes this function, in the sense of . The algorithm, the constant of the time bound O((ℓ+1) · (n+1)³) and the constant of the length bound come first, so both constants are absolute. The input is the pair (G, S), with the encodings of . A graph has the vertices , and the notions of chains and construction sequences are applied to its .
The width of item 1 is the radius-r width of , which counts parts. The length bound O(n w₁) is spelled out as K · (n+1) · (w₁+1). The number w_r is , with π_G the neighborhood complexity . Item 2 is 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 (). 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 asks of its output.
Builds on
Used by
none
From Mathlib
none
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments