Computing chains of small width

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

    There is an algorithm which, given an n-vertex graph G, a radius r ∈ β„• and a rational Ξ΅ > 0, computes a chain of G of length O(r/Ξ΅) and radius-r width O_{π’ž,r,Ξ΅}(n^Ξ΅), and runs in time Γ”_{π’ž,r}(nΒ³), where π’ž is any monadically dependent graph class containing G. Here Γ”_k(n^c) stands for a bound O_{k,Ξ΄}(n^{c+Ξ΄}) for every Ξ΄ > 0.

    The paper cites this as Theorem 4.4 of the companion paper Monadically dependent graph classes have almost bounded merge-width (see Lax185574.ChainTheoremLax185574.ChainTheorem).

    Concept map
    13 concepts
    100%
    Proven claimDefinitionThis conceptRelated conceptA β†’ B: B builds on A
    Evidence

    Each proof establishes this claim relative to its assumptions.

    In the paper

    • page 30 of this submission's paper

    Lean source view on GitHub

    1import Lax185574.Chains
    2import Lax185574.Algorithms
    3import Lax185574.MonadicDependence
    4import Mathlib.Analysis.SpecialFunctions.Pow.Real
    5
    6/-!
    7---
    8title: Computing chains of small width
    9type: theorem
    10---
    11There is an algorithm which, given an n-vertex graph G, a radius r ∈ β„•
    12and a rational Ξ΅ > 0, computes a chain of G of length O(r/Ξ΅) and radius-r
    13width O_{π’ž,r,Ξ΅}(n^Ξ΅), and runs in time Γ”_{π’ž,r}(nΒ³), where π’ž is any
    14monadically dependent graph class containing G. Here Γ”_k(n^c) stands for
    15a bound O_{k,Ξ΄}(n^{c+Ξ΄}) for every Ξ΄ > 0.
    16
    17The paper cites this as Theorem 4.4 of the companion paper
    18*Monadically dependent graph classes have almost bounded merge-width*
    19(see `Lax185574.ChainTheorem`).
    20
    21# Formalization notes
    22
    23The radius is at least 1, which is the case used. The chain is
    24produced by a function `chain` of r, Ξ΅ and the graph, and the algorithm
    25`A` computes this function, in the sense of `Lax185574.Algorithms`. The
    26algorithm and the absolute constant `K` of the length bound come first.
    27On every graph the output is a chain of length at most K Β· r/Ξ΅ + K. The
    28algorithm does not depend on the class. For a monadically dependent
    29class π’ž, a radius r and Ξ΅, the constant `c` bounds the width by
    30c Β· (n+1)^Ξ΅ on the members of π’ž. The input is the triple (r, Ξ΅, G) and
    31the output is the list of the sets of the chain. The chain is listed in
    32increasing order, βˆ… = S₁ βŠ† β‹― βŠ† S_m = V(G), as in `Lax185574.Chains`.
    33This is the reverse of the order of the paper.
    34
    35**Deviation from the paper.** The paper claims the running time
    36Γ”_{π’ž,r}(nΒ³), whose constant does not depend on Ξ΅. Here the time bound
    37is O(n^{3+Ξ΄}) on members of π’ž for every Ξ΄ > 0, with a constant c
    38depending on π’ž, r, Ξ΅ and Ξ΄, as in `Lax185574.ChainTheorem`. This is
    39weaker than the paper and is what `Lax185574.DefinableSequences`
    40needs. A caller chooses Ξ΄ independently of Ξ΅, so that the time fits the
    41word lengths of its own statement. The statement is the companion
    42paper's theorem with the chain reversed. The word lengths at which the
    43statement speaks also depend on the class, through c, as in
    44`Lax185574.DefinableSequences`.
    45-/
    46
    47namespace Lax185574.ComputingChains
    48
    49open Lax185574.Graphs Lax185574.MonadicDependence Lax185574.Algorithms Lax185574.Chains
    50
    51/-- **Computing chains.** One algorithm computes, from `r β‰₯ 1`, a
    52rational `Ξ΅ > 0` and a graph, a chain of length at most `K Β· r/Ξ΅ + K`. On
    53members of a monadically dependent class, the chain has radius-`r` width
    54at most `c Β· (n+1)^Ξ΅`, and for every `Ξ΄ > 0` the algorithm takes time
    55`O(n^(3+Ξ΄))`, with `c` depending also on `Ξ΄`. -/
    56axiom exists_program_chain :
    57 βˆƒ (A : Algorithm) (K : β„•) (chain : β„• β†’ β„š β†’ (G : Graph) β†’ List (Finset (Fin G.n))),
    58 (βˆ€ (r : β„•) (Ξ΅ : β„š) (G : Graph), 1 ≀ r β†’ 0 < Ξ΅ β†’
    59 IsChain (chain r Ξ΅ G) ∧ ((chain r Ξ΅ G).length : β„š) ≀ K * r / Ξ΅ + K) ∧
    60 βˆ€ C : GraphClass, MonadicallyDependent C β†’ βˆ€ (r : β„•) (Ξ΅ : β„š), 1 ≀ r β†’ 0 < Ξ΅ β†’
    61 βˆ€ Ξ΄ : ℝ, 0 < Ξ΄ β†’ βˆƒ c : β„•, βˆ€ G ∈ C,
    62 (chainWidth G.toSimpleGraph r (chain r Ξ΅ G) : ℝ) ≀ c * ((G.n : ℝ) + 1) ^ (Ξ΅ : ℝ) ∧
    63 A.Computes c (r, Ξ΅, G) (chain r Ξ΅ G) ((G.n : ℝ) ^ (3 + Ξ΄))
    64
    65end Lax185574.ComputingChains
    66
    Show Proof
    Formalization notes

    The radius is at least 1, which is the case used. The chain is produced by a function chainchain of r, Ξ΅ and the graph, and the algorithm AA computes this function, in the sense of Lax185574.AlgorithmsLax185574.Algorithms. The algorithm and the absolute constant KK of the length bound come first. On every graph the output is a chain of length at most K Β· r/Ξ΅ + K. The algorithm does not depend on the class. For a monadically dependent class π’ž, a radius r and Ξ΅, the constant cc bounds the width by c Β· (n+1)^Ξ΅ on the members of π’ž. The input is the triple (r, Ξ΅, G) and the output is the list of the sets of the chain. The chain is listed in increasing order, βˆ… = S₁ βŠ† β‹― βŠ† S_m = V(G), as in Lax185574.ChainsLax185574.Chains. This is the reverse of the order of the paper.

    Deviation from the paper. The paper claims the running time Γ”_{π’ž,r}(nΒ³), whose constant does not depend on Ξ΅. Here the time bound is O(n^{3+Ξ΄}) on members of π’ž for every Ξ΄ > 0, with a constant c depending on π’ž, r, Ξ΅ and Ξ΄, as in Lax185574.ChainTheoremLax185574.ChainTheorem. This is weaker than the paper and is what Lax185574.DefinableSequencesLax185574.DefinableSequences needs. A caller chooses Ξ΄ independently of Ξ΅, so that the time fits the word lengths of its own statement. The statement is the companion paper's theorem with the chain reversed. The word lengths at which the statement speaks also depend on the class, through c, as in Lax185574.DefinableSequencesLax185574.DefinableSequences.

    Discussion

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

    Loading discussion…