Chains of vertex sets with few atomic types in flip-metric balls

Lax185574.ChainTheorem Β· concepts/Lax185574/ChainTheorem.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 ∈ β„• 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
    12 concepts
    100%
    Proven claimDefinitionThis conceptRelated conceptA β†’ B: B builds on A
    Evidence

    Each proof establishes this claim relative to its assumptions.

    Lean source view on GitHub

    1import Lax185574.Flips
    2import Lax185574.Algorithms
    3import Lax185574.MonadicDependence
    4import Mathlib.Analysis.SpecialFunctions.Pow.Real
    5
    6/-!
    7---
    8title: Chains of vertex sets with few atomic types in flip-metric balls
    9type: theorem
    10---
    11Let r ∈ β„• and π’ž be a monadically dependent graph class. Then for any
    12rational Ξ΅ > 0 and an n-vertex graph G ∈ π’ž, there is a sequence of
    13vertex subsets
    14
    15βˆ… = B_m βŠ† B_{mβˆ’1} βŠ† β‹― βŠ† B₁ βŠ† Bβ‚€ = V(G)
    16
    17with m ≀ O(r/Ξ΅) that satisfies the following condition: for every
    18i ∈ [m] and u ∈ V(G), Ball^r_{𝒯₁(G,B_i)}[u] intersects at most
    19O_{π’ž,r,Ξ΅}(n^Ξ΅) parts of 𝒯₁(G, B_{iβˆ’1}). Moreover, given Ξ΅, r and G, such
    20a sequence Bβ‚€, B₁, …, B_m can be computed in Γ•_{π’ž,r}(nΒ³) time.
    21
    22This 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
    25partition 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
    30In the companion paper β„• is the set of positive integers, so r β‰₯ 1. Its
    311-types over B are the atomic types over B, `Partitions.atomicTypes`,
    32and its flips and flip-metric balls are those of `Lax185574.Flips`,
    33with distances measured by shortest paths. A sequence Bβ‚€, …, B_m is the
    34list [Bβ‚€, …, B_m], in the order of the companion paper, which is the
    35reverse of the order of chains in `Lax185574.Chains`. The bound m ≀
    36O(r/Ξ΅) on the number of steps becomes a bound K Β· r/Ξ΅ + K on the length
    37m + 1 of the list.
    38
    39The algorithm `A` is chosen before the class, and the sequence is a
    40function `chain` of r, Ξ΅ and the graph that `A` computes, in the sense
    41of `Lax185574.Algorithms`. The companion paper notes that the algorithm
    42of its Damping Theorem does not depend on the class, and the algorithm
    43of this theorem iterates it. The bound on the length in its proof uses only the Damping Theorem for
    44the graph at hand, which holds for every graph with that graph's own
    45constants (every graph lies in the monadically dependent class {G}).
    46The proof gives m ≀ 1 + 2r/Ξ΅ on every graph with at least two vertices,
    47and graphs with at most one vertex are handled directly. So the length
    48bound is stated for every graph. The input is the triple (r, Ξ΅, G) and
    49the output is the list of sets.
    50
    51The 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
    53constant c chosen after π’ž, r, Ξ΅ and Ξ΄. In the companion paper the time
    54bound does not depend on Ξ΅, so this is weaker. The width bound is
    55c Β· (n+1)^Ξ΅ with the same constant.
    56
    57The algorithm of the companion paper uses integers of n^{o(1)} bits.
    58Stored in several words, they cost a subpolynomial factor, which the
    59bound O(n^{3+Ξ΄}) absorbs, so the word lengths are those of
    60`Lax185574.Algorithms`, with the word-length exponent of the algorithm,
    61which is chosen before the class.
    62-/
    63
    64namespace Lax185574.ChainTheorem
    65
    66open Lax185574.Graphs Lax185574.MonadicDependence Lax185574.Algorithms
    67open Lax185574.Partitions Lax185574.Flips
    68
    69universe z
    70
    71variable {V : Type z}
    72
    73/-- `B` is a decreasing sequence of vertex sets `V = Bβ‚€ βŠ‡ B₁ βŠ‡ β‹― βŠ‡ B_m = βˆ…`. -/
    74def 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`
    79in the metric of `B_i`-flips meets at most `K` parts of the partition
    80into atomic types over `B_{iβˆ’1}`. -/
    81def 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,
    87from `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
    89monadically dependent class, every radius-`r` ball of the `B_i`-flip
    90metric meets at most `c Β· (n+1)^Ξ΅` atomic types over `B_{iβˆ’1}`, and the
    91algorithm takes time `O(n^(3+Ξ΄))` for every `Ξ΄ > 0`. -/
    92axiom 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
    101end Lax185574.ChainTheorem
    102
    Show Proof
    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, Partitions.atomicTypesPartitions.atomicTypes, and its flips and flip-metric balls are those of Lax185574.FlipsLax185574.Flips, 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 Lax185574.ChainsLax185574.Chains. 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 AA is chosen before the class, and the sequence is a function chainchain of r, Ξ΅ and the graph that AA computes, in the sense of Lax185574.AlgorithmsLax185574.Algorithms. 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 Lax185574.AlgorithmsLax185574.Algorithms, with the word-length exponent of the algorithm, which is chosen before the class.

    Discussion

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

    Loading discussion…