Band-jump decompositions of cubic graphs (conditional) #
Assume the band clusters of the Gaussian edge-score field are subcritical
(BandSubcritical, an open percolation hypothesis). Then for every c > 0 and every slack
ξ > 0, every large simple cubic graph on h vertices has a path decomposition whose bags
have at most (exp (-c²/2) p + ξ) h + 1 vertices, where
p = (3/(2π)) arccos ((1 + 2√2)/4) is the frontier coefficient of Gaussian.Frontier.
The decomposition is the band-jump order of Gaussian.Band.Order for the edge scores of one
Gaussian sample, with the band clusters as blocks. Outside the band [-c, c) a vertex
straddles a threshold t with probability at most exp (-t²/2) p by the threshold-decay
crossing bound (Gaussian.Edge.Decay), and |t| ≥ c there; a grid on each side and the
second-moment bound control every threshold of one sample. Inside the band a bag also holds
the vertices of one block. Such a block lies in one band cluster, which either has at most
K vertices or consists of vertices in clusters of more than K vertices; by the hypothesis
and Markov's inequality the latter number at most 2 η h for some sample. Taking K
negligible against h gives the coefficient.
At c = 4/25 the doubled coefficient is at most 5/18, the graph-ordering coefficient of
the circuit bound 23/5.
Band-jump cubic pathwidth (conditional on BandSubcritical). If the band clusters
are subcritical for every decay rate q < 1/√2 and radius R, then for every positive slack
ξ, every sufficiently large simple cubic graph on h vertices has a path decomposition with
bags of at most (exp (-c²/2) · (3/(2π)) arccos ((1 + 2√2)/4) + ξ) h + 1 vertices.
At c = 4/25 the doubled band-jump coefficient 2 exp (-c²/2) p is at most 5/18.