Gaussian edge-score decompositions of cubic graphs #
Every large simple cubic graph has a path decomposition whose bags have at most
((3/(2π)) arccos ((1 + 2√2)/4) + ξ) h vertices, for every slack ξ > 0. The coefficient
(3/(2π)) arccos ((1 + 2√2)/4) ≈ 0.14035 is well below the 1/6 of the Fomin–Høie bound.
Each edge uv receives the Gaussian score ⟨(x_u + x_v)/‖x_u + x_v‖, ω⟩, where x are the
normalized truncated distance-kernel rows of Gaussian.Layout; the edges are listed by score,
and a vertex stays in the bags between its first and last edge (Gaussian.Frontier.Order).
A vertex therefore occupies the bag at threshold t exactly when t separates two of its
three edge scores, which happens with probability at most half the summed crossing
probabilities of its edge pairs; by Sheppard's bound (Gaussian.Edge.Exact) a pair with
correlation ρ' crosses any threshold with probability at most arccos ρ' / π. The three edge vectors at a vertex lie within correlation
√((1 + ρ)/2) of the vertex row, where ρ bounds the kernel correlation of adjacent rows;
since ‖Σ y_e‖ ≥ ⟨Σ y_e, x_v⟩, their average pairwise correlation is at least (1 + 3ρ)/4,
and concavity of arccos (Gaussian.Frontier.Arccos) bounds the summed angles. With
ρ → 2√2/3 the per-vertex probability is at most (3/(2π)) arccos ((1 + 2√2)/4), the
coefficient above. A threshold grid and the second-moment bound control every bag of one
sample, as for the cutwidth layout.
Gaussian cubic pathwidth. For every positive slack ξ, every sufficiently large
simple cubic graph on h vertices has a path decomposition with bags of at most
((3/(2π)) arccos ((1 + 2√2)/4) + ξ) h + 1 vertices.
The frontier coefficient is positive.
The doubled frontier coefficient, the graph-ordering coefficient of this decomposition,
is at most 9/32.