Computing locally definable construction sequences

Lax185574.DefinableSequences Β· concepts/Lax185574/DefinableSequences.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

    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
    16 concepts
    100%
    Proven claimDefinitionThis conceptRelated conceptA β†’ B: B builds on A
    Evidence

    In the paper

    • page 16 of this submission's paper

    Lean source view on GitHub

    1import Lax185574.LocalDefinability
    2import Lax185574.ConstructionSequences
    3import Lax185574.MonadicDependence
    4import Lax185574.Algorithms
    5import Mathlib.Analysis.SpecialFunctions.Pow.Real
    6
    7/-!
    8---
    9title: Computing locally definable construction sequences
    10type: theorem
    11---
    12Let r β‰₯ 1 be an integer, Ξ΅ > 0 a rational, and π’ž a monadically
    13dependent graph class. There is a constant Ξ΄ β‰₯ 1 depending only on π’ž
    14such that every n-vertex graph G ∈ π’ž has a construction sequence of G
    15which is radius-r definable with O(r/Ξ΅) unary predicates,
    16O_{π’ž,r,Ξ΅}(n^{δΡ}) parameters and quantifier rank 7, and has length
    17O_{π’ž,r,Ξ΅}(n^{1+δΡ}). Moreover, there is an algorithm (independent of π’ž)
    18which, given r, Ξ΅ and G, computes such a sequence, and runs in time
    19Γ”_{π’ž,r,Ξ΅}(nΒ³) whenever G ∈ π’ž. Here Γ”_k(nΒ³) stands for a bound
    20O_{k,Ξ·}(n^{3+Ξ·}) for every Ξ· > 0.
    21
    22# Formalization notes
    23
    24The construction sequence is produced by a function `script` of r, Ξ΅
    25and the graph, as a script of `Lax185574.ConstructionSequences`, and
    26the algorithm `A` computes this function, in the sense of
    27`Lax185574.Algorithms`. The algorithm, the function and the absolute
    28constant `K` of the bound O(r/Ξ΅) on the number of predicates come first,
    29so none of them depends on the class. On every graph, the script gives
    30a construction sequence of the graph. The input of the algorithm is the
    31triple (r, Ξ΅, G), with the encodings of `Lax185574.Encodings`.
    32
    33The constant Ξ΄ of the paper is `a`. It is chosen after the class and
    34before r and Ξ΅. The time bound Γ”_{π’ž,r,Ξ΅}(nΒ³) is spelled out as
    35`n^(3+Ξ·)` for every real Ξ· > 0, with the constant `c` depending on π’ž,
    36r, Ξ΅ and Ξ·. The same `c` bounds the sequence. The bounds on the
    37sequence do not involve Ξ·, so a single Ξ·, say Ξ· = 1, gives a constant
    38for them. The number of unary predicates is at most `⌈K Β· r/Ξ΅βŒ‰ + K`,
    39which is O(r/Ξ΅) in the sense of the paper, including its additive
    40constant.
    41
    42Every graph belongs to some monadically dependent class, for instance
    43the class containing it alone. So the algorithm computes the script of
    44every graph, at every word length admissible for the constant of some
    45class that contains it.
    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. The algorithm can ensure it by giving the vertices of the initial
    50partial graph the colors 0, …, n βˆ’ 1, since steps only use colors that
    51occur.
    52-/
    53
    54namespace Lax185574.DefinableSequences
    55
    56open Lax185574.Graphs Lax185574.MonadicDependence Lax185574.Algorithms
    57open Lax185574.ConstructionSequences Lax185574.LocalDefinability
    58
    59/-- **Locally definable construction sequences.** One algorithm
    60computes, from `r β‰₯ 1`, a rational `Ξ΅ > 0` and a graph `G`, a
    61construction sequence of `G`, given by its script. On members of a
    62monadically 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
    64radius-`r` definable with `⌈KΒ·r/Ξ΅βŒ‰ + K` unary predicates,
    65`⌊c Β· (n+1)^(aΞ΅)βŒ‹` parameters and quantifier rank `7`. Here `a β‰₯ 1`
    66depends only on the class, and `c` on the class, `r`, `Ξ΅` and `Ξ·`. -/
    67axiom 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
    80end Lax185574.DefinableSequences
    81
    Show Proof
    Formalization notes

    The construction sequence is produced by a function scriptscript of r, Ξ΅ and the graph, as a script of Lax185574.ConstructionSequencesLax185574.ConstructionSequences, and the algorithm AA computes this function, in the sense of Lax185574.AlgorithmsLax185574.Algorithms. The algorithm, the function and the absolute constant KK 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 Lax185574.EncodingsLax185574.Encodings.

    The constant Ξ΄ of the paper is aa. It is chosen after the class and before r and Ξ΅. The time bound Γ”_{π’ž,r,Ξ΅}(nΒ³) is spelled out as n(3+Ξ·)n^(3+Ξ·) for every real Ξ· > 0, with the constant cc depending on π’ž, r, Ξ΅ and Ξ·. The same cc 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 ⌈Kβ‹…r/Ξ΅βŒ‰+K⌈K Β· r/Ξ΅βŒ‰ + K, 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 (Script.HasSmallNumbersScript.HasSmallNumbers). 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.

    Loading discussion…