Boundary Complexity of Structured Objects: Exact Ratios, Phase Transitions, and DAS Classification

We study the ratio R(D) = K(∂D)/K(D) between the Kolmogorov complexity of an object’s boundary and the object itself. We prove: (T1) Repetition theorem: R(pn) = K0/(K0 + c log n), with phase transition at n∗ = eK0/c from boundary-dominated (R > 1/2) to core-dominated (R < 1/2). (T2) Graph lower bound: K(∂Gn) = Ω(n) for Gn ∼ G(n, 1/2) via vertex expansion, giving R(Gn) = Θ(1/n). (T3) b-ary tree limit (new): R(Tb,d) → (b − 1)/b as d → ∞, with exact formula R(Tb,d) = bd/bd+1−1. Binary trees (b = 2) are the only critical case (R → 1/2); for b ≥ 3 b−1 the tree is always boundary-dominated. All results are verified numerically.