Gray Cycles of Maximum Length Related to k-Character Substitutions
This work addresses a theoretical problem in combinatorics and coding theory, focusing on incremental improvements in understanding Gray cycles.
The paper tackles the problem of determining the maximum length of Gray cycles under k-character substitutions, computing the bound λ(n) for all alphabet sizes and word lengths.
Given a word binary relation $τ$ we define a $τ$-Gray cycle over a finite language X to be a permutation w [i] 0$\le$i$\le$|X|--1 of X such that each word wi is an image of the previous word wi--1 by $τ$. In that framework, we introduce the complexity measure $λ$(n), equal to the largest cardinality of a language X having words of length at most n, and such that a $τ$-Gray cycle over X exists. The present paper is concerned with the relation $τ$ = $σ$ k , the so-called k-character substitution, where (u, v) belongs to $σ$ k if, and only if, the Hamming distance of u and v is k. We compute the bound $λ$(n) for all cases of the alphabet cardinality and the argument n.