The Discrepancy of the Lex-Least De Bruijn Sequence

Simple item page
dc.creatorCooper, Joshua
dc.creatorHeitsch, Christine
dc.date2009-03-22
dc.date.accessioned2026-07-07T12:55:36Z
dc.date.available2026-07-07T12:55:36Z
dc.descriptionWe answer the following question of R. L. Graham: What is the discrepancy of the lexicographically-least binary de Bruijn sequence? Here, "discrepancy" refers to the maximum (absolute) difference between the number of ones and the number of zeros in any initial segment of the sequence. We show that the answer is $Θ(2^n \log n/n)$.
dc.description11 pages, 0 figures
dc.identifierhttps://arxiv.org/abs/0903.3753
dc.identifierhttp://arxiv.org/abs/0903.3753
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/224302
dc.subjectCombinatorics
dc.subject05A16 (Primary) 05D40, 68R15 (Secondary)
dc.titleThe Discrepancy of the Lex-Least De Bruijn Sequence
dc.typetext

Files

Collections

arXiv