Uniform bounds on the sizes of welded-tree color classes
ProvedWeldedPath.weld_color_class_card_boundsfinite-combinatoricsgraph-theorywelded-trees
In any valid properly three-colored welded-tree instance of height , each weld-color class has between and edges. The bound holds for every color and every middle-column parameter . The formal statement uses the original colored edge set, so it also bounds the size of each matching coordinate in the product distribution.
Preamble
import Definitions.Def_WeldedPath_bEdge
Formal statement
namespace WeldedPath
theorem weld_color_class_card_bounds (n l : ℕ) (G : WeldedInstance n) (hG : G.IsValid)
(hn : 1 ≤ n) (α : Fin 3) :
2 ^ (n - 1) ≤ (G.classEdges l (.wld α)).card ∧
(G.classEdges l (.wld α)).card ≤ 2 ^ n := by
sorry
end WeldedPath
Source
Carolan, Childs, Coudron, Gilani, Miloschewsky, Podder, Algorithmic Wave-Particle Duality: Pathfinding in Welded Trees is Hard, https://arxiv.org/html/2611.05912v1#S3.SS1, Lemma 3.2 and equation (22); see also Section 4.4, the definition of m_eta before equation (76). This is a coarse explicit consequence of those counts. The supplied proof instead uses proper coloring, leaf sibling pairs, and endpoint injections, and works for every n>=1 without a parity hypothesis.