A Cycle Joining Construction of the Prefer-Max De Bruijn Sequence

2021/04/07 by Amram, Gal, Rubin, Amir, Weiss, Gera
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.2104.02999

Abstract

We propose a novel construction for the well-known prefer-max De Bruijn sequence, based on the cycle joining technique. We further show that the construction implies known results from the literature in a straightforward manner. First, it implies the correctness of the onion theorem, stating that, effectively, the reverse of prefer-max is in fact an infinite De Bruijn sequence. Second, it implies the correctness of recently discovered shift rules for prefer-max, prefer-min, and their reversals. Lastly, it forms an alternative proof for the seminal FKM-theorem.

Related

• An Efficient Shift Rule for the Prefer-Max De Bruijn Sequence
• To Infinity and Beyond: Continuing De Bruijn Sequences by Extending the Alphabet
• An Efficient Generalized Shift-Rule for the Prefer-Max De Bruijn Sequence
• Efficient constructions of the Prefer-same and Prefer-opposite de Bruijn sequences
• De Bruijn Sequences: From Games to Shift-Rules to a Proof of the Fredricksen-Kessler-Maiorana Theorem