Path decompositions and the cubic pathwidth bound

A path decomposition of a simple graph is a sequence of bags covering every vertex and every edge, in which the bags containing a fixed vertex are consecutive. Its width is one less than the largest bag.

PathwidthBound p ξ N₀ states a pathwidth bound with coefficient p for cubic graphs: every simple 3-regular graph on more than N₀ vertices has a path decomposition of width at most (p + ξ) h, where h is the number of vertices. Together with the compression and median-ordering arguments it yields the graph-ordering hypothesis Multigraph.OrderingBound (2 p). PathDecomposition.Bisection proves the bound with p = 1/6 from a cubic bisection bound, and Bisection.Helpful supplies the sharp bound for every positive slack.

The cut of a vertex set in a simple graph, SimpleGraph.cutFinset, is the set of edges with exactly one endpoint in the set. CutwidthBound c ξ N₀ states a cutwidth bound with coefficient c for cubic graphs: every simple 3-regular graph on more than N₀ vertices has a vertex ordering all of whose prefix cuts have at most (c + ξ) h edges. It yields Multigraph.OrderingBound (2 c) by ordering the cubic core with the key itself instead of a median ordering.

structure Algebraic.Cutwidth.PathDecomposition {W : Type} (H : SimpleGraph W) : Type

A path decomposition: bags indexed by Fin length, covering every vertex and every edge, with the bags containing any vertex forming an interval.

• length : ℕ

  The number of bags.

• bag : Fin self.length → Finset W

  The bags.

• vertex_mem (w : W) : ∃ (i : Fin self.length), w ∈ self.bag i

  Every vertex lies in some bag.

• edge_mem (u v : W) : H.Adj u v → ∃ (i : Fin self.length), u ∈ self.bag i ∧ v ∈ self.bag i

  Both endpoints of every edge lie in a common bag.

• consecutive (w : W) (i j k : Fin self.length) : i ≤ j → j ≤ k → w ∈ self.bag i → w ∈ self.bag k → w ∈ self.bag j

  The bags containing a vertex are consecutive.

def Algebraic.Cutwidth.PathDecomposition.trivial {W : Type} (H : SimpleGraph W) [Fintype W] : PathDecomposition H

The one-bag decomposition of a finite graph.

Equations

• Algebraic.Cutwidth.PathDecomposition.trivial H = { length := 1, bag := fun (x : Fin 1) => Finset.univ, vertex_mem := ⋯, edge_mem := ⋯, consecutive := ⋯ }

def Algebraic.Cutwidth.PathwidthBound (p ξ : ℝ) (N₀ : ℕ) : Prop

The pathwidth bound for cubic graphs with coefficient p, slack ξ, and threshold N₀: every simple 3-regular graph on h > N₀ vertices has a path decomposition all of whose bags have at most (p + ξ) h + 1 vertices. The Fomin–Høie bound has p = 1/6.

Equations

• One or more equations did not get rendered due to their size.

noncomputable def SimpleGraph.cutFinset {W : Type} (H : SimpleGraph W) [Fintype W] (S : Finset W) : Finset (Sym2 W)

The edges of a simple graph with exactly one endpoint in S.

Equations

• H.cutFinset S = {e ∈ H.edgeFinset | ∃ (a : W) (b : W), e = s(a, b) ∧ a ∈ S ∧ b ∉ S}

theorem SimpleGraph.mem_cutFinset {W : Type} (H : SimpleGraph W) [Fintype W] {S : Finset W} {e : Sym2 W} : e ∈ H.cutFinset S ↔ e ∈ H.edgeSet ∧ ∃ (a : W) (b : W), e = s(a, b) ∧ a ∈ S ∧ b ∉ S

theorem SimpleGraph.mem_cutFinset_mk {W : Type} (H : SimpleGraph W) [Fintype W] {S : Finset W} {a b : W} : s(a, b) ∈ H.cutFinset S ↔ H.Adj a b ∧ (a ∈ S ∧ b ∉ S ∨ b ∈ S ∧ a ∉ S)

An edge crossing a set is adjacent-pair witnessed with the inside endpoint first.

theorem SimpleGraph.cutFinset_eq_empty_of_subsingleton {W : Type} (H : SimpleGraph W) [Fintype W] [Subsingleton W] (S : Finset W) : H.cutFinset S = ∅

A graph with at most one vertex has no crossing edges.

def Algebraic.Cutwidth.CutwidthBound (c ξ : ℝ) (N₀ : ℕ) : Prop

The cutwidth bound for cubic graphs with coefficient c, slack ξ, and threshold N₀: every simple 3-regular graph on h > N₀ vertices has an injective vertex key all of whose prefixes {w | key w < t} are crossed by at most (c + ξ) h edges.

Equations

• One or more equations did not get rendered due to their size.