Paper IIII: Unbounded Exact-Trace Confinement Gaps for Finite-Direction Lattice Spanning Paths

Résumé fourni par la source

We study a lattice spanning-path problem in which the prescribed object is not merely a set of points to be visited, but the exact host-vertex trace of the path. In the language of spanning-versus-covering paths, the free model permits auxiliary (Steiner) vertices only outside a fixed host while preserving the same prescribed host trace and direction alphabet.Let U be a finite set of primitive unoriented directions in Z^2, and let H = {(x,y) in Z^2 : y >= 0} be the fixed upper half-plane. For a finite set S contained in H, the confined cost K_H(S;U) is the minimum number of turns of a vertex-simple U-path whose complete vertex set is exactly S. The free cost K_free(S;U) allows the path to leave H, but requires its trace on H to remain exactly S.The main result gives a complete classification for finite direction alphabets: unbounded additive and multiplicative confinement gaps exist if and only if U contains at least two nonparallel orientations. More precisely, whenever U contains two nonparallel directions, there is an admissible family S_n with K_free(S_n;U) bounded independently of n, while K_H(S_n;U) tends to infinity.As a concrete example, for the eight-direction alphabet {(1,0), (0,1), (1,+/-1), (1,+/-2), (2,+/-1)}, we exhibit a family R_p with |R_p| = 2p - 1, K_free(R_p) = 2, and K_H(R_p) = 2p - 4 for every even p >= 4. Thus both the additive confinement gap and the confinement ratio are unbounded.

Ce résumé expose les affirmations des auteurs. BNTIC ne l’interprète pas comme une validation indépendante des résultats.