Theorem 8.22 — four leveled-graph goodness criteria
OpenSparseDisc.Supplement.theorem_8_22graph-theoryp2o-gran-per-chapterp2o-plan-paperp2o-v1sparse-discrepancy
Let be a finite leveled graph with positive integer levels.
- A forest is good when no two level- vertices are adjacent.
- If is triangle-free, no vertex has two neighbours on a cycle avoiding it, and each block contains at most one level- vertex, then is good. Consequently such graphs are -good; this includes triangle-free outerplanar graphs, triangle-free graphs in which no vertex has two neighbours of degree at least , and graphs obtained by subdividing every edge of a simple graph at least twice.
- If vertices in are pairwise nonadjacent and have no common neighbour, is a forest, and is independent, then is -good.
- Let and . If has an ordering with at most later neighbours in , each has neighbours in , and the induced leveled graph on with level is good, then is -good.
These clauses preserve the non-uniform levels and every named graph class in the source.
Differences from the source:
- encoding: forest, triangle-free, cycles avoiding a vertex and block level counts → Mathlib acyclicity and clique-freeness, cycle walks whose support avoids the vertex, and finite filters over the published block predicate; reason: standard finite simple-graph encodings of the source conditions
- encoding: and the level → disjoint finite vertex sets covering
univ, with the induced subtype graph on and natural level subtraction guarded by ; reason: Lean encoding preserves positivity and the exact non-uniform levels - encoding: graphs obtained by subdividing each edge at least twice → isomorphism to the published subdivision construction with at least two inserted vertices per original edge; reason: Lean convention, same graph class
Preamble
import Mathlib import Definitions.Def_SparseDisc_IsLevelGood import Definitions.Def_SparseDisc_IsCGood import Definitions.Def_SparseDisc_IsBlock import Definitions.Def_TaitTobin_Outerplanar_Setting import Definitions.Def_SparseDisc_Supplement_IsSubdivisionAtLeastTwice import Definitions.Def_SparseDisc_Supplement_NoTwoNeighboursOnAvoidingCycle import Definitions.Def_SparseDisc_Supplement_HasLaterBoundOn
Formal statement
namespace SparseDisc.Supplement
open Classical in
/-- **Theorem 8.22** (Zeng–Cao–Dai–Wang–Liao, *Sparse Discrepancy Beyond Additive Functions*, STOC
2027 submission manuscript (sha256 0f09ec60…25b81), p.38). All four leveled-graph goodness
criteria are stated, together with every graph-class consequence listed in part (b).
**Formalization Note** Forest means Mathlib `IsAcyclic`; triangle-free means `CliqueFree 3`.
Blocks are the published `SparseDisc.IsBlock`. In part (d), `V₁,V₂` are an explicit partition,
`q_v` is the number of neighbours of `v` in `V₁`, and the induced graph on `V₂` carries the
non-uniform level `C-q_v`. -/
theorem theorem_8_22 :
(∀ (V : Type) [Fintype V] [DecidableEq V] (G : SimpleGraph V) (ℓ : V → ℕ),
(∀ v, 1 ≤ ℓ v) → (∀ u v, G.Adj u v → ¬ (ℓ u = 1 ∧ ℓ v = 1)) →
G.IsAcyclic → SparseDisc.IsLevelGood G ℓ) ∧
(∀ (V : Type) [Fintype V] [DecidableEq V] (G : SimpleGraph V) (ℓ : V → ℕ),
(∀ v, 1 ≤ ℓ v) → G.CliqueFree 3 → NoTwoNeighboursOnAvoidingCycle G →
(∀ W : Finset V, SparseDisc.IsBlock G W →
(W.filter (fun v => ℓ v = 1)).card ≤ 1) → SparseDisc.IsLevelGood G ℓ) ∧
(∀ (V : Type) [Fintype V] [DecidableEq V] (G : SimpleGraph V),
G.CliqueFree 3 → NoTwoNeighboursOnAvoidingCycle G → SparseDisc.IsCGood G 2) ∧
(∀ (V : Type) [Fintype V] [DecidableEq V] (G : SimpleGraph V),
G.CliqueFree 3 → TaitTobin.Outerplanar.IsOuterplanar G → SparseDisc.IsCGood G 2) ∧
(∀ (V : Type) [Fintype V] [DecidableEq V] (G : SimpleGraph V),
G.CliqueFree 3 →
(∀ v, (Finset.univ.filter (fun w => G.Adj v w ∧ 3 ≤ G.degree w)).card ≤ 1) →
SparseDisc.IsCGood G 2) ∧
(∀ (V : Type) [Fintype V] [DecidableEq V] (G : SimpleGraph V),
IsSubdivisionAtLeastTwice G → SparseDisc.IsCGood G 2) ∧
(∀ (V : Type) [Fintype V] [DecidableEq V] (G : SimpleGraph V) (D : Finset V),
(∀ u ∈ D, ∀ v ∈ D, u ≠ v →
¬ G.Adj u v ∧ ¬ ∃ w, G.Adj u w ∧ G.Adj v w) →
(G.induce ({v | v ∉ D} : Set V)).IsAcyclic →
(∀ u v, (∃ d ∈ D, G.Adj d u) → (∃ d ∈ D, G.Adj d v) →
G.Adj u v → False) → SparseDisc.IsCGood G 2) ∧
(∀ (C : ℕ), 2 ≤ C → ∀ (V : Type) [Fintype V] [DecidableEq V]
(G : SimpleGraph V) (V₁ V₂ : Finset V), Disjoint V₁ V₂ → V₁ ∪ V₂ = Finset.univ →
HasLaterBoundOn G V₁ (C - 1) →
(∀ v ∈ V₂, (V₁.filter (fun u => G.Adj v u)).card ≤ C - 1) →
SparseDisc.IsLevelGood (G.induce (V₂ : Set V))
(fun v => C - (V₁.filter (fun u => G.Adj v.1 u)).card) →
SparseDisc.IsCGood G (C : ℝ)) := by sorry
end SparseDisc.Supplement
Source
Zeng–Cao–Dai–Wang–Liao, Sparse Discrepancy Beyond Additive Functions, STOC 2027 submission (manuscript sha256 0f09ec60…), Theorem 8.22, p.38