Computing chains of small width
Lax185574.ComputingChains Β· concepts/Lax185574/ComputingChains.lean Β· lax-185574
No public endorsements yet.
Loading reviewβ¦
Sign in with ORCIDNatural 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 ).
Concept map
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
| 1 | import Lax185574.Chains |
| 2 | import Lax185574.Algorithms |
| 3 | import Lax185574.MonadicDependence |
| 4 | import Mathlib.Analysis.SpecialFunctions.Pow.Real |
| 5 | |
| 6 | /-! |
| 7 | --- |
| 8 | title: Computing chains of small width |
| 9 | type: theorem |
| 10 | --- |
| 11 | There is an algorithm which, given an n-vertex graph G, a radius r β β |
| 12 | and a rational Ξ΅ > 0, computes a chain of G of length O(r/Ξ΅) and radius-r |
| 13 | width O_{π,r,Ξ΅}(n^Ξ΅), and runs in time Γ_{π,r}(nΒ³), where π is any |
| 14 | monadically dependent graph class containing G. Here Γ_k(n^c) stands for |
| 15 | a bound O_{k,Ξ΄}(n^{c+Ξ΄}) for every Ξ΄ > 0. |
| 16 | |
| 17 | The 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 | |
| 23 | The radius is at least 1, which is the case used. The chain is |
| 24 | produced by a function `chain` of r, Ξ΅ and the graph, and the algorithm |
| 25 | `A` computes this function, in the sense of `Lax185574.Algorithms`. The |
| 26 | algorithm and the absolute constant `K` of the length bound come first. |
| 27 | On every graph the output is a chain of length at most K Β· r/Ξ΅ + K. The |
| 28 | algorithm does not depend on the class. For a monadically dependent |
| 29 | class π, a radius r and Ξ΅, the constant `c` bounds the width by |
| 30 | c Β· (n+1)^Ξ΅ on the members of π. The input is the triple (r, Ξ΅, G) and |
| 31 | the output is the list of the sets of the chain. The chain is listed in |
| 32 | increasing order, β = Sβ β β― β S_m = V(G), as in `Lax185574.Chains`. |
| 33 | This 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 |
| 37 | is O(n^{3+Ξ΄}) on members of π for every Ξ΄ > 0, with a constant c |
| 38 | depending on π, r, Ξ΅ and Ξ΄, as in `Lax185574.ChainTheorem`. This is |
| 39 | weaker than the paper and is what `Lax185574.DefinableSequences` |
| 40 | needs. A caller chooses Ξ΄ independently of Ξ΅, so that the time fits the |
| 41 | word lengths of its own statement. The statement is the companion |
| 42 | paper's theorem with the chain reversed. The word lengths at which the |
| 43 | statement speaks also depend on the class, through c, as in |
| 44 | `Lax185574.DefinableSequences`. |
| 45 | -/ |
| 46 | |
| 47 | namespace Lax185574.ComputingChains |
| 48 | |
| 49 | open Lax185574.Graphs Lax185574.MonadicDependence Lax185574.Algorithms Lax185574.Chains |
| 50 | |
| 51 | /-- **Computing chains.** One algorithm computes, from `r β₯ 1`, a |
| 52 | rational `Ξ΅ > 0` and a graph, a chain of length at most `K Β· r/Ξ΅ + K`. On |
| 53 | members of a monadically dependent class, the chain has radius-`r` width |
| 54 | at most `c Β· (n+1)^Ξ΅`, and for every `Ξ΄ > 0` the algorithm takes time |
| 55 | `O(n^(3+Ξ΄))`, with `c` depending also on `Ξ΄`. -/ |
| 56 | axiom 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 | |
| 65 | end Lax185574.ComputingChains |
| 66 |
Formalization notes
The radius is at least 1, which is the case used. The chain is produced by a function of r, Ξ΅ and the graph, and the algorithm computes this function, in the sense of . The algorithm and the absolute constant 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 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 . 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 . This is weaker than the paper and is what 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 .
Used by
none
From Mathlib
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments