Gaussian layouts of cubic graphs #
Every large simple cubic graph has a vertex ordering whose prefix cuts have at most
((3/π)(3 - 2√2) + ξ) h edges, for any slack ξ > 0. The coefficient
(3/π)(3 - 2√2) ≈ 0.16384 is below the 1/6 of the Monien–Preis bisection and
Fomin–Høie pathwidth bounds.
The ordering sorts Gaussian scores X_v = ⟨â_v, ω⟩, where â_v is the normalized
truncated distance kernel z ↦ q ^ dist(v, z) (radius R) and ω has independent
standard Gaussian coordinates. Adjacent kernel rows have correlation at least
2q/(1+q²) - 3(2q²)^R in every graph of maximum degree three
(Gaussian.sum_unitKernel_mul_ge), so each threshold separates an edge with probability at
most (2/π)√((1-ρ)/(1+ρ)) (Gaussian.gaussPi_between_le). A threshold grid, the locality
of the kernel, and a second-moment bound (Gaussian.pi_deviation_le) control all
prefixes of one sample simultaneously.
The limiting correlation 2√2/3 is that of the Gaussian wave functions on the 3-regular
tree studied by Csóka, Gerencsér, Harangi, and Virág (Invariant Gaussian processes and
independent sets on regular graphs of large girth, 2015) and used by Lyons (Factors of
IID on trees, 2017) for bisections of random cubic graphs. The truncated kernel and its
correlation bound for every graph of maximum degree three are developed here.
Gaussian cubic cutwidth. For every positive slack ξ, every sufficiently large
simple cubic graph on h vertices has an injective vertex key whose prefix cuts have at
most ((3/π)(3 - 2√2) + ξ) h edges.
The Gaussian cutwidth coefficient is positive.
The doubled coefficient (6/π)(3 - 2√2) is the graph-ordering coefficient; it is at
most 20/61, hence below 1/3.