Connectivity of Subsequence-Embedding Exchange Graphs and Finite Certificates for a Periodic Deletion Model

Abstract We investigate exchange graphs associated with embeddings of a fixed subsequence into a finite word. Vertices represent deletion masks yielding the same retained word, and two vertices are adjacent when one deleted position is exchanged with one retained position without changing the resulting subsequence. We establish a constructive connectivity theorem for arbitrary finite words: every embedding of a fixed retained word can be transformed into its canonical leftmost embedding through a sequence of admissible single-position exchanges. Consequently, every nonempty reconstruction fiber is connected, and any two embeddings of a retained word of length (k) can be joined by at most (2k) admissible exchanges. We then investigate the periodic sequence [ P=(0,1,2,4,7,3,2,6,0,7,8,7). ] For deletion counts (r\leq 6), we establish a locality theorem showing that every admissible single exchange has span strictly less than 12. Exact computational audits classify the reconstruction fibers for one and two periods with five or six deletions. The observed component structures include isolated vertices, edges, three-vertex paths, triangles, and four-cycles. An explicit eight-vertex hypercube component is additionally certified for three periods. The results combine constructive proofs with reproducible finite computational certificates. The universal connectivity theorem is presented without a claim of historical priority, and the complete graph-isomorphism classification for arbitrary numbers of periods remains open. Keywords: subsequence embeddings; exchange graphs; deletion masks; connectivity; greedy alignment; periodic words; graph components; reconstruction theory; computational combinatorics. Scientific Status and Scope This manuscript is an author-approved mathematical preprint associated with the RT-ACTIVE-PHYLLOTAXIS 6.0 research program. The universal fiber-connectivity theorem and its constructive path-length bound are established by mathematical argument. The periodic locality result is supported by a counting proof. The finite component classifications are supported by reproducible Python computations. The manuscript does not claim a complete classification of reconstruction-fiber graphs for arbitrary period counts. Historical priority and originality of the universal connectivity theorem have not been conclusively established. The manuscript has undergone AI-assisted mathematical and bibliographic review but has not been externally peer reviewed. Author Approval: GRANTED. This designation records the author's requested publication authorization and does not constitute independent identity verification or an external review endorsement. Declaration of AI Assistance OpenAI ChatGPT was used substantially in mathematical exploration, programming, computational certificate design, literature scouting, proof auditing, and manuscript drafting. The named author, Ivo Vajc, is responsible for reviewing the mathematical arguments, checking the released source code and computational results, independently verifying bibliographic references and originality claims, and making the final decision concerning publication. AI assistance does not constitute independent external peer review. Responsibility for the published manuscript and its scientific claims remains with the named author.