Chains of vertex sets with few atomic types in flip-metric balls
Lax185574.ChainTheorem Β· concepts/Lax185574/ChainTheorem.lean Β· lax-185574
No public endorsements yet.
Loading reviewβ¦
Sign in with ORCIDNatural Language Statement
Theorem
Let r β β and π be a monadically dependent graph class. Then for any rational Ξ΅ > 0 and an n-vertex graph G β π, there is a sequence of vertex subsets
β = B_m β B_{mβ1} β β― β Bβ β Bβ = V(G)
with m β€ O(r/Ξ΅) that satisfies the following condition: for every i β [m] and u β V(G), Ball^r_{π―β(G,B_i)}[u] intersects at most O_{π,r,Ξ΅}(n^Ξ΅) parts of π―β(G, B_{iβ1}). Moreover, given Ξ΅, r and G, such a sequence Bβ, Bβ, β¦, B_m can be computed in Γ_{π,r}(nΒ³) time.
This is Theorem 4.4 of Dreier, MΓ€hlmann, Pilipczuk and ToruΕczyk, Monadically dependent graph classes have almost bounded merge-width (2026), the companion paper. Here π―β(G, B) is the partition of V(G) into 1-types over B, that is, into atomic types, and Ball^r_π«[u] is the radius-r ball of the π«-flip metric.
Concept map
Evidence
Each proof establishes this claim relative to its assumptions.
Lean source view on GitHub
| 1 | import Lax185574.Flips |
| 2 | import Lax185574.Algorithms |
| 3 | import Lax185574.MonadicDependence |
| 4 | import Mathlib.Analysis.SpecialFunctions.Pow.Real |
| 5 | |
| 6 | /-! |
| 7 | --- |
| 8 | title: Chains of vertex sets with few atomic types in flip-metric balls |
| 9 | type: theorem |
| 10 | --- |
| 11 | Let r β β and π be a monadically dependent graph class. Then for any |
| 12 | rational Ξ΅ > 0 and an n-vertex graph G β π, there is a sequence of |
| 13 | vertex subsets |
| 14 | |
| 15 | β = B_m β B_{mβ1} β β― β Bβ β Bβ = V(G) |
| 16 | |
| 17 | with m β€ O(r/Ξ΅) that satisfies the following condition: for every |
| 18 | i β [m] and u β V(G), Ball^r_{π―β(G,B_i)}[u] intersects at most |
| 19 | O_{π,r,Ξ΅}(n^Ξ΅) parts of π―β(G, B_{iβ1}). Moreover, given Ξ΅, r and G, such |
| 20 | a sequence Bβ, Bβ, β¦, B_m can be computed in Γ_{π,r}(nΒ³) time. |
| 21 | |
| 22 | This is Theorem 4.4 of Dreier, MΓ€hlmann, Pilipczuk and ToruΕczyk, |
| 23 | *Monadically dependent graph classes have almost bounded merge-width* |
| 24 | (2026), the companion paper. Here π―β(G, B) is the |
| 25 | partition of V(G) into 1-types over B, that is, into atomic types, and Ball^r_π«[u] is the radius-r ball of the |
| 26 | π«-flip metric. |
| 27 | |
| 28 | # Formalization notes |
| 29 | |
| 30 | In the companion paper β is the set of positive integers, so r β₯ 1. Its |
| 31 | 1-types over B are the atomic types over B, `Partitions.atomicTypes`, |
| 32 | and its flips and flip-metric balls are those of `Lax185574.Flips`, |
| 33 | with distances measured by shortest paths. A sequence Bβ, β¦, B_m is the |
| 34 | list [Bβ, β¦, B_m], in the order of the companion paper, which is the |
| 35 | reverse of the order of chains in `Lax185574.Chains`. The bound m β€ |
| 36 | O(r/Ξ΅) on the number of steps becomes a bound K Β· r/Ξ΅ + K on the length |
| 37 | m + 1 of the list. |
| 38 | |
| 39 | The algorithm `A` is chosen before the class, and the sequence is a |
| 40 | function `chain` of r, Ξ΅ and the graph that `A` computes, in the sense |
| 41 | of `Lax185574.Algorithms`. The companion paper notes that the algorithm |
| 42 | of its Damping Theorem does not depend on the class, and the algorithm |
| 43 | of this theorem iterates it. The bound on the length in its proof uses only the Damping Theorem for |
| 44 | the graph at hand, which holds for every graph with that graph's own |
| 45 | constants (every graph lies in the monadically dependent class {G}). |
| 46 | The proof gives m β€ 1 + 2r/Ξ΅ on every graph with at least two vertices, |
| 47 | and graphs with at most one vertex are handled directly. So the length |
| 48 | bound is stated for every graph. The input is the triple (r, Ξ΅, G) and |
| 49 | the output is the list of sets. |
| 50 | |
| 51 | The time bound Γ_{π,r}(nΒ³) hides a subpolynomial factor that depends on |
| 52 | π and r. It is spelled out as O(n^{3+Ξ΄}) for every real Ξ΄ > 0, with a |
| 53 | constant c chosen after π, r, Ξ΅ and Ξ΄. In the companion paper the time |
| 54 | bound does not depend on Ξ΅, so this is weaker. The width bound is |
| 55 | c Β· (n+1)^Ξ΅ with the same constant. |
| 56 | |
| 57 | The algorithm of the companion paper uses integers of n^{o(1)} bits. |
| 58 | Stored in several words, they cost a subpolynomial factor, which the |
| 59 | bound O(n^{3+Ξ΄}) absorbs, so the word lengths are those of |
| 60 | `Lax185574.Algorithms`, with the word-length exponent of the algorithm, |
| 61 | which is chosen before the class. |
| 62 | -/ |
| 63 | |
| 64 | namespace Lax185574.ChainTheorem |
| 65 | |
| 66 | open Lax185574.Graphs Lax185574.MonadicDependence Lax185574.Algorithms |
| 67 | open Lax185574.Partitions Lax185574.Flips |
| 68 | |
| 69 | universe z |
| 70 | |
| 71 | variable {V : Type z} |
| 72 | |
| 73 | /-- `B` is a decreasing sequence of vertex sets `V = Bβ β Bβ β β― β B_m = β `. -/ |
| 74 | def IsDecreasingChain [Fintype V] (B : List (Finset V)) : Prop := |
| 75 | β h : B β [], B.head h = Finset.univ β§ B.getLast h = β β§ |
| 76 | β (t : β) (ht : t + 1 < B.length), B[t + 1] β B[t] |
| 77 | |
| 78 | /-- For every `i β [m]` and vertex `u`, the radius-`r` ball around `u` |
| 79 | in the metric of `B_i`-flips meets at most `K` parts of the partition |
| 80 | into atomic types over `B_{iβ1}`. -/ |
| 81 | def BallsMeetFewTypes (G : SimpleGraph V) (r : β) (K : β) (B : List (Finset V)) : Prop := |
| 82 | β (t : β) (ht : t + 1 < B.length) (u : V), |
| 83 | (partCount (atomicTypes G (B[t] : Set V)) |
| 84 | (flipBall G (atomicTypes G (B[t + 1] : Set V)) r u) : β) β€ K |
| 85 | |
| 86 | /-- **Chain theorem of the companion paper.** One algorithm computes, |
| 87 | from `r β₯ 1`, a rational `Ξ΅ > 0` and a graph, a decreasing sequence |
| 88 | `V = Bβ β β― β B_m = β ` of length at most `K Β· r/Ξ΅ + K`. On members of a |
| 89 | monadically dependent class, every radius-`r` ball of the `B_i`-flip |
| 90 | metric meets at most `c Β· (n+1)^Ξ΅` atomic types over `B_{iβ1}`, and the |
| 91 | algorithm takes time `O(n^(3+Ξ΄))` for every `Ξ΄ > 0`. -/ |
| 92 | axiom exists_program_decreasingChain : |
| 93 | β (A : Algorithm) (K : β) (chain : β β β β (G : Graph) β List (Finset (Fin G.n))), |
| 94 | (β (r : β) (Ξ΅ : β) (G : Graph), 1 β€ r β 0 < Ξ΅ β |
| 95 | IsDecreasingChain (chain r Ξ΅ G) β§ ((chain r Ξ΅ G).length : β) β€ K * r / Ξ΅ + K) β§ |
| 96 | β C : GraphClass, MonadicallyDependent C β β (r : β) (Ξ΅ : β), 1 β€ r β 0 < Ξ΅ β |
| 97 | β Ξ΄ : β, 0 < Ξ΄ β β c : β, β G β C, |
| 98 | BallsMeetFewTypes G.toSimpleGraph r (c * ((G.n : β) + 1) ^ (Ξ΅ : β)) (chain r Ξ΅ G) β§ |
| 99 | A.Computes c (r, Ξ΅, G) (chain r Ξ΅ G) ((G.n : β) ^ (3 + Ξ΄)) |
| 100 | |
| 101 | end Lax185574.ChainTheorem |
| 102 |
Formalization notes
In the companion paper β is the set of positive integers, so r β₯ 1. Its 1-types over B are the atomic types over B, , and its flips and flip-metric balls are those of , with distances measured by shortest paths. A sequence Bβ, β¦, B_m is the list [Bβ, β¦, B_m], in the order of the companion paper, which is the reverse of the order of chains in . The bound m β€ O(r/Ξ΅) on the number of steps becomes a bound K Β· r/Ξ΅ + K on the length m + 1 of the list.
The algorithm is chosen before the class, and the sequence is a function of r, Ξ΅ and the graph that computes, in the sense of . The companion paper notes that the algorithm of its Damping Theorem does not depend on the class, and the algorithm of this theorem iterates it. The bound on the length in its proof uses only the Damping Theorem for the graph at hand, which holds for every graph with that graph's own constants (every graph lies in the monadically dependent class {G}). The proof gives m β€ 1 + 2r/Ξ΅ on every graph with at least two vertices, and graphs with at most one vertex are handled directly. So the length bound is stated for every graph. The input is the triple (r, Ξ΅, G) and the output is the list of sets.
The time bound Γ_{π,r}(nΒ³) hides a subpolynomial factor that depends on π and r. It is spelled out as O(n^{3+Ξ΄}) for every real Ξ΄ > 0, with a constant c chosen after π, r, Ξ΅ and Ξ΄. In the companion paper the time bound does not depend on Ξ΅, so this is weaker. The width bound is c Β· (n+1)^Ξ΅ with the same constant.
The algorithm of the companion paper uses integers of n^{o(1)} bits. Stored in several words, they cost a subpolynomial factor, which the bound O(n^{3+Ξ΄}) absorbs, so the word lengths are those of , with the word-length exponent of the algorithm, which is chosen before the class.
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