Longest subsequences shared by two de Bruijn sequences

An order n binary de Bruijn sequence is a periodic sequence of bits with period 2 ⁿ in which each n-tuple of bits occurs exactly once. We consider the longest subsequences shared by two de Bruijn sequences. First, we fix one de Bruijn sequence and prove that de Bruijn sequences sharing a longest subsequence with it must be those obtained by a single cross-join operation from it. Then determining such sequences is equivalent to finding cross-join pairs with maximum diameter. Second, we prove that for n≥ 5 , there exist two de Bruijn sequences of order n sharing a subsequence of length 2 ⁿ- 2 , i.e., there exists sequence a0a1⋯a2n-3 with length 2 ⁿ- 2 such that both a0a1⋯a2n-301 and a0a1⋯a2n-310 are periods of de Bruijn sequences.