Computing locally definable construction sequences
Lax185574.DefinableSequences Β· concepts/Lax185574/DefinableSequences.lean Β· lax-185574
No public endorsements yet.
Loading reviewβ¦
Sign in with ORCIDNatural Language Statement
Theorem
Let r β₯ 1 be an integer, Ξ΅ > 0 a rational, and π a monadically dependent graph class. There is a constant Ξ΄ β₯ 1 depending only on π such that every n-vertex graph G β π has a construction sequence of G which is radius-r definable with O(r/Ξ΅) unary predicates, O_{π,r,Ξ΅}(n^{δΡ}) parameters and quantifier rank 7, and has length O_{π,r,Ξ΅}(n^{1+δΡ}). Moreover, there is an algorithm (independent of π) which, given r, Ξ΅ and G, computes such a sequence, and runs in time Γ_{π,r,Ξ΅}(nΒ³) whenever G β π. Here Γ_k(nΒ³) stands for a bound O_{k,Ξ·}(n^{3+Ξ·}) for every Ξ· > 0.
Concept map
Evidence
Each proof establishes this claim relative to its assumptions.
In the paper
- page 16 of this submission's paper
Lean source view on GitHub
| 1 | import Lax185574.LocalDefinability |
| 2 | import Lax185574.ConstructionSequences |
| 3 | import Lax185574.MonadicDependence |
| 4 | import Lax185574.Algorithms |
| 5 | import Mathlib.Analysis.SpecialFunctions.Pow.Real |
| 6 | |
| 7 | /-! |
| 8 | --- |
| 9 | title: Computing locally definable construction sequences |
| 10 | type: theorem |
| 11 | --- |
| 12 | Let r β₯ 1 be an integer, Ξ΅ > 0 a rational, and π a monadically |
| 13 | dependent graph class. There is a constant Ξ΄ β₯ 1 depending only on π |
| 14 | such that every n-vertex graph G β π has a construction sequence of G |
| 15 | which is radius-r definable with O(r/Ξ΅) unary predicates, |
| 16 | O_{π,r,Ξ΅}(n^{δΡ}) parameters and quantifier rank 7, and has length |
| 17 | O_{π,r,Ξ΅}(n^{1+δΡ}). Moreover, there is an algorithm (independent of π) |
| 18 | which, given r, Ξ΅ and G, computes such a sequence, and runs in time |
| 19 | Γ_{π,r,Ξ΅}(nΒ³) whenever G β π. Here Γ_k(nΒ³) stands for a bound |
| 20 | O_{k,Ξ·}(n^{3+Ξ·}) for every Ξ· > 0. |
| 21 | |
| 22 | # Formalization notes |
| 23 | |
| 24 | The construction sequence is produced by a function `script` of r, Ξ΅ |
| 25 | and the graph, as a script of `Lax185574.ConstructionSequences`, and |
| 26 | the algorithm `A` computes this function, in the sense of |
| 27 | `Lax185574.Algorithms`. The algorithm, the function and the absolute |
| 28 | constant `K` of the bound O(r/Ξ΅) on the number of predicates come first, |
| 29 | so none of them depends on the class. On every graph, the script gives |
| 30 | a construction sequence of the graph. The input of the algorithm is the |
| 31 | triple (r, Ξ΅, G), with the encodings of `Lax185574.Encodings`. |
| 32 | |
| 33 | The constant Ξ΄ of the paper is `a`. It is chosen after the class and |
| 34 | before r and Ξ΅. The time bound Γ_{π,r,Ξ΅}(nΒ³) is spelled out as |
| 35 | `n^(3+Ξ·)` for every real Ξ· > 0, with the constant `c` depending on π, |
| 36 | r, Ξ΅ and Ξ·. The same `c` bounds the sequence. The bounds on the |
| 37 | sequence do not involve Ξ·, so a single Ξ·, say Ξ· = 1, gives a constant |
| 38 | for them. The number of unary predicates is at most `βK Β· r/Ξ΅β + K`, |
| 39 | which is O(r/Ξ΅) in the sense of the paper, including its additive |
| 40 | constant. |
| 41 | |
| 42 | Every graph belongs to some monadically dependent class, for instance |
| 43 | the class containing it alone. So the algorithm computes the script of |
| 44 | every graph, at every word length admissible for the constant of some |
| 45 | class that contains it. |
| 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. The algorithm can ensure it by giving the vertices of the initial |
| 50 | partial graph the colors 0, β¦, n β 1, since steps only use colors that |
| 51 | occur. |
| 52 | -/ |
| 53 | |
| 54 | namespace Lax185574.DefinableSequences |
| 55 | |
| 56 | open Lax185574.Graphs Lax185574.MonadicDependence Lax185574.Algorithms |
| 57 | open Lax185574.ConstructionSequences Lax185574.LocalDefinability |
| 58 | |
| 59 | /-- **Locally definable construction sequences.** One algorithm |
| 60 | computes, from `r β₯ 1`, a rational `Ξ΅ > 0` and a graph `G`, a |
| 61 | construction sequence of `G`, given by its script. On members of a |
| 62 | monadically dependent class it takes time `O(n^(3+Ξ·))` for every |
| 63 | `Ξ· > 0`, and the sequence has length at most `c Β· (n+1)^(1+aΞ΅)` and is |
| 64 | radius-`r` definable with `βKΒ·r/Ξ΅β + K` unary predicates, |
| 65 | `βc Β· (n+1)^(aΞ΅)β` parameters and quantifier rank `7`. Here `a β₯ 1` |
| 66 | depends only on the class, and `c` on the class, `r`, `Ξ΅` and `Ξ·`. -/ |
| 67 | axiom exists_program_definableSequence : |
| 68 | β (A : Algorithm) (K : β) (script : β β β β (G : Graph) β Script G.n), |
| 69 | (β (r : β) (Ξ΅ : β) (G : Graph), 1 β€ r β 0 < Ξ΅ β |
| 70 | IsConstructionSequence G.toSimpleGraph (script r Ξ΅ G).run β§ |
| 71 | (script r Ξ΅ G).HasSmallNumbers) β§ |
| 72 | β C : GraphClass, MonadicallyDependent C β β a : β, 1 β€ a β§ |
| 73 | β (r : β) (Ξ΅ : β), 1 β€ r β 0 < Ξ΅ β β Ξ· : β, 0 < Ξ· β β c : β, |
| 74 | β G β C, |
| 75 | A.Computes c (r, Ξ΅, G) (script r Ξ΅ G) ((G.n : β) ^ (3 + Ξ·)) β§ |
| 76 | ((script r Ξ΅ G).run.length : β) β€ c * ((G.n : β) + 1) ^ (1 + (a : β) * Ξ΅) β§ |
| 77 | IsRadiusDefinable G.toSimpleGraph (script r Ξ΅ G).run r (β(K : β) * r / Ξ΅ββ + K) |
| 78 | β(c : β) * ((G.n : β) + 1) ^ ((a : β) * Ξ΅)ββ 7 |
| 79 | |
| 80 | end Lax185574.DefinableSequences |
| 81 |
Formalization notes
The construction sequence is produced by a function of r, Ξ΅ and the graph, as a script of , and the algorithm computes this function, in the sense of . The algorithm, the function and the absolute constant of the bound O(r/Ξ΅) on the number of predicates come first, so none of them depends on the class. On every graph, the script gives a construction sequence of the graph. The input of the algorithm is the triple (r, Ξ΅, G), with the encodings of .
The constant Ξ΄ of the paper is . It is chosen after the class and before r and Ξ΅. The time bound Γ_{π,r,Ξ΅}(nΒ³) is spelled out as for every real Ξ· > 0, with the constant depending on π, r, Ξ΅ and Ξ·. The same bounds the sequence. The bounds on the sequence do not involve Ξ·, so a single Ξ·, say Ξ· = 1, gives a constant for them. The number of unary predicates is at most , which is O(r/Ξ΅) in the sense of the paper, including its additive constant.
Every graph belongs to some monadically dependent class, for instance the class containing it alone. So the algorithm computes the script of every graph, at every word length admissible for the constant of some class that contains it.
Every number in the encoding of the script is at most the length of the encoding plus n (). The paper does not say this. The algorithm can ensure it by giving the vertices of the initial partial graph the colors 0, β¦, n β 1, since steps only use colors that occur.
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments