Observations on de Bruijn graphs

Abstract (Swedish)

Abstract of chapter 1
For n >= 2 the number of mixing n-step subshifts of finite type (sft) over the alphabet {0, 1} is proven to be at least 15/16 times the number of transitive n-step sfts. A conjecture assumes the latter to be at least 2^(3*2^(n-1)-n).

Abstract of chapter 2
The alternating colouring function is defined. Strings over the alphabet {0, 1} are divided in colourable and non-colourable ones. The points in the subshift of finite type defined by forbidding all non-colourable strings of a certain length alternate between states of one colour and states of the other colour. The number of non-colourable strings of length n >= 2 is proven to be 2 * (J_(n-2) + 1) where J is the sequence of Jacobsthal numbers.

Popular Abstract (Swedish)

En oändlig lång kedja av A:n och B:n får man föreställa sig som en
papperslapp där det står A:n och B:n på, dess ena sida man håller i
handen men som sträcker sig över horisonten utan att sluta någonstans.
Eller som en miniräknare som visar ett nytt tecken varje sekund. Eller
en skrivare med oändlig tillgång till papper och bläck men som tyvärr
bara skriver ut A:n och B:n. En sådan oändlig lång kedja kallas för en
som har ändlig längd kallas för . En bokstavsföljd skulle kunna börja så
här:

Än så länge är varje bokstavskombination (av A:n och B:n) möjlig.
Urvalet ska nu begränsas: Man kan till exempel förbjuda ordet AA. Det
betyder att det aldrig kan förekomma två A:n direkt efter varandra.
Bokstavsföljden består då av en massa B:n som bara ibland bryts av
enskilda A:n:

Istället skulle man också kunna förbjuda ordet AB. Trots att det igen
förbjuds ett ord av längd 2 är effekten betydligt större: Så snart det
förekommer ett A i bokstavsföljden kommer A:na fortsätta i all evighet
för det finns aldrig en möjlighet att byta tillbaka till ett B. De enda
bokstavsföljder som fortfarande är tillåtna är

- bokstavsföljden som bara innehåller A:n,

- bokstavsföljden som bara innehåller B:n och

- en sådan som börjar med ett visst antal B:n och fortsätter med
oändligt många A:n:

Genom att förbjuda längre ord och flera samtidigt kan man påverka
bokstavsföljden lite mer subtilt: Att förbjuda orden AAA och ABA till
exempel har nästan inga konsekvenser för hur bokstavsföljden kommer att
se ut. Alla ord med längd 2 är fortfarande tillåtna och kan förekomma i
valfri ordningsföljd i bokstavsföljden:

Annars är det när man förbjuder ordet BAA: Ordet AA kan då fortfarande
förekomma i början av bokstavsföljden, sedan dock aldrig igen:

När man förbjuder ord av en viss längd kan man genom detta i praktiken
alltså även förbjuda kortare ord. Det kallas för att man
bokstavsföljden. Nu kan man uttrycka det som sades innan på följande
vis: "Att förbjuda AB eller BAA bryter bokstavsföljden, att förbjuda AA
eller AAA och ABA gör inte det."

Kapitel 2

Nu får varje ord en färg. Som exempel ska ord av längd 3 betraktas.
Initialerna av orden AAA och ABA färgas röda; initialerna av orden AAB,
BAA och BAB blåa. En bokstavsföljd skulle kunna börja såhär: Varje
bokstav är färgad enligt ordet av längd 3 vars initial den är: Första
ordet av längd 3 är AAA så första bokstaven är röd. Andra ordet är AAB
så andra bokstaven är blå. De sista två bokstäverna går inte att färgas
eftersom färgen beror alltid på de två bokstäverna som följer efter.

Att röda och blåa bokstäver alternerar är inget slump utan målet med
färgningen. Frågan som
kapitel 2 tittar på är: Vilka ord borde man färga röda
och vilka blåa för att få ett sådant alternerande mönster i
bokstavsföljden?

För många bokstavsföljder går det över huvud taget inte. In en sådan som
börjar med kommer de första två bokstäverna alltid ha samma färg.
Lösningen är här att förbjuda ordet AAAA. Likaså får man såklart
förbjuda ordet BBBB. Det visar sig att inte ens det räcker: Man behöver
även förbjuda orden ABBA och BAAB för att hitta ett sätt. Det beskrivs i
den följande tabellen:

Röda färgade Blåa färgade Förbjudna
-------------- -------------- -----------
AAA AAB AAAA
ABA ABB ABBA
BAA BAB BAAB
BBA BBB BBBB

En färgad bokstavsföljd skulle då kunna börja såhär:

Man inser: Två ord av längd 3 som har ett jämnt antal bokstäver emellan
sig måste alltid har olika färger. Står däremot ett udda tal bokstäver
emellan dem så har de samma färg. När ett ord förekommer två gånger i
bokstavsföljden måste det alltså finnas ett udda tal bokstäver mellan
dem. Annars skulle samma ord först ha en färg och sedan en annan.

Kapitel 1

Att samtidigt förbjuda orden AAAA, ABBA, BAAB och BBBB bryter inte
bokstavsföljden; alla ord av längd 3 är fortfarande tillåtna och det i
valfri ordning. De är dock bundna till vissa positioner. Ovanligt är att
begränsningen kvarstår oavsett hur långt man går i bokstavsföljden.

Att förbjuda några ord leder ofta till en viss minimiavsstånd mellan de
orden som fortfarande är tillåtna. Förbjuder man ordet AAA till exempel
måste det alltid finnas ett B mellan ett AA och det nästa. Efter
minimiavståndet kan ordet dock förekommer igen när som helst. Det gäller
inte när man förbjuder AAAA, ABBA, BAAB och BBBB: Även om man går 100
steg vidare, 1000 eller en miljon: Där får inte stå ett AAA, helt enkelt
för 100, 1000 och en miljon är jämna tal och mellan ett AAA och ett
annat så måste det alltid finnas ett udda antal bokstäver.

Inskränkningar som strukturerar bokstavsföljden för alltid sägs .

Hur många sätt finns det att förhindra blandning utan att bryta
bokstavsföljden? Svaret ges i
kapitel 1: Finns inte särskilt många. Om man inte bryter
bokstavsföljden så förhindras blandning i mindre än 1 av 16 fall.

Popular Abstract

Imagine an of characters A and B. Such can be thought of as a paper
strip with As and Bs written on it, one end of which one holds in the
hand while the other stretches over the horizon without ever ending. Or
as a calculator that displays a new character each second. Or as a
printer with an infinite amount of paper and ink that unfortunately only
prints As and Bs. In contrast to infinite strings there are also that
have a finite length. An infinite string could for instance start like
this:

At this stage any combination (of As and Bs) is possible. The variety
shall now be shrunk: For example one can forbid the finite string AA.
That means there can never be an A that follows directly on another A.
The infinite string consists then of mostly Bs that are just sometimes
interrupted by single As:

Instead one could also forbid the string AB. Although even here just a
string of length 2 is forbidden the effect is considerably larger: As
soon as there is an A in the infinite string the As have to continue
forever because there will never be a possibility to switch back to a B.
The only infinite strings still permitted would be

- the infinite string that only contains As,

- the infinite string that only contains Bs and

- an infinite string that starts with a certain number of Bs and
continues with infinitely many As:

By forbidding longer words and several at the same time on can influence
the infinite string more subtly: Forbidding the words AAA and ABA for
example almost does not have consequences for the appearance of the
infinite string. All strings of length 2 are still permitted and can
occur in arbitrary order in the infinite string:

Not so if one forbids the word BAA: The string AA can still occur in the
beginning of the infinite string but then never again:

By forbidding strings of a certain length it is hence possible to even
forbid shorter strings in practice. Such is called the infinite string.
Using that terminology what has been previously explained can now be put
the following way: "Forbidding AB or BAA disconnects the infinite
string, forbidding AA or AAA and ABA does not."

Chapter 2

Now each finite string gets a colour. As an example the strings of
length 3 shall be considered. The first letter of the strings AAA and
ABA are coloured red; the first letters of the words AAB, BAA and BAB
blue. An infinite string could start like this: Each character is
coloured according to the string of length 3 whose first letter it is:
The first string of length 3 is AAA so the first character is red. The
second string is AAB so the second character is blue. The last two
characters cannot be coloured yet because their colour would depend on
the two characters succeeding them.

That red and blue characters alternate is not a coincidence but the very
intent with this colouring. The question
chapter 2 investigates is: Which finite strings should
be coloured red and which ones blue to get such an alternating pattern
in the infinite string?

For many infinite strings that is just impossible. The first two
characters of an infinite word starting with will always have the same
colour. The solution is here to forbid the string AAAA. Analogously of
course one also has to forbid the word BBBB. It turns out that that is
not enough either: One also has to forbid the words ABBA and BAAB to
find a colouring. It is outlined in the following table:

Coloured red Coloured blue Forbidden
-------------- --------------- -----------
AAA AAB AAAA
ABA ABB ABBA
BAA BAB BAAB
BBA BBB BBBB

A coloured infinite string could then look like this:

Note that two words of length 3 that have an even number of characters
between them must always have different colours. Conversely if there is
an odd number of characters between them, they have the same colour. If
a finite string occurs twice in the infinite string there has to be an
odd number of characters between them. Otherwise the same finite string
would first have one colour and later another.

Chapter 1

Forbidding AAAA, ABBA, BAAB and BBBB does not disconnect the infinite
string; all strings of length 3 are still permitted and so they are in
arbitrary order. They are however bound to certain positions. What is
unusual, the restrictions are valid no matter how far one goes in the
infinite string.

Forbidding some finite strings often leads to a certain minimum distance
between those that are still allowed. If one forbids the string AAA for
example there must always be a B between one AA and the next. After that
minimum distance however the string AA can again occur at any point.
That is not the case when forbidding AAAA, ABBA, BAAB and BBBB: Even if
one goes 100 steps further, 1000 or a million: Right there an AAA won't
be allowed, just because 100, 1000 and a million are even numbers and
between an AAA and the next there must be an odd number of characters.

Constrains that structure the infinite string forever are said to .

How many ways are there to prevent mixing without disconnecting the
infinite string? The answer is given in
chapter 1: There aren't that many. If the infinite string
does not get disconnected in less than 1 out of 16 cases mixing is
prevented.

Popular Abstract (German)

Man denke sich eine unendlich lange Aneinanderreihung der Buchstaben A
und B. Das kann man sich vorstellen wie einen Papierstreifen auf dem As
und Bs stehen, dessen Anfang man in der Hand hält, der sich aber über
den Horizont erstreckt und nie endet. Oder wie einen Taschenrechner, der
jede Sekunde ein neues Zeichen anzeigt. Oder einen Drucker mit
unendlichem Vorrat an Papier und Toner, der aber leider nur As und Bs
druckt. Ein solche unendlich lange Aneinanderreihung wird genannt, eine
endlich lange dagegen ein . Eine Buchstabenfolge könnte zum Beispiel
folgendermaßen beginnen:

Bisher ist jede beliebe Buchstabenkombination (von As und Bs) möglich.
Die Auswahl soll jetzt eingeschränkt werden: Man kann zum Beispiel das
Wort AA verbieten. Das bedeutet, dass nie ein A auf ein anderes folgen
kann. Die Buchstabenfolge besteht aus einem Haufen Bs, nur manchmal von
einzelnen As unterbrochen:

Stattdessen könnte man auch das Wort AB ausschließen. Obwohl auch hier
nur ein Wort der Länge 2 verboten wird, sind die Auswirkungen viel
weitreichender: Sobald ein A in der Buchstabenfolge auftaucht, werden
sich As bis in alle Ewigkeit fortziehen, da es nie die Möglichkeit gibt,
wieder zu einem B zurückzukehren. Die einzigen Buchstabenfolgen, die
jetzt noch möglich sind, sind

- die Buchstabenfolge, die ausschließlich aus As besteht,

- die Buchstabenfolge, die ausschließlich aus Bs besteht und

- eine solche, die mit einer bestimmten Anzahl Bs anfängt und sich
dann mit unendlich vielen As fortsetzt:

Indem man längere Wörter verbietet, und mehrere gleichzeitig, kann man
die Buchstabenfolge subtiler beeinflussen: Das Verbieten der Wörter AAA
und ABA zum Beispiel hat kaum Auswirkungen auf das Aussehen der
Buchstabenfolge. Alle Wörter der Länge 2 sind noch erlaubt und können in
beliebiger Reihenfolge in der Buchstabenfolge vorkommen:

Anders sieht das aus, wenn man das Wort BAA verbietet: Das Wort AA kann
dann zwar ganz am Anfang der Buchstabenfolge vorkommen, dann aber nie
wieder:

Wenn man Wörter einer bestimmten Länge verbietet, kann man damit also
praktisch auch kürzere Wörter verbieten. In dem Fall wird gesagt, man
die Buchstabenfolge. Mit diesem Vokabular lässt sich das bisher gesagte
folgendermaßen ausdrücken: "Das Verbieten von AB oder BAA zerreißt die
Buchstabenfolge, das Verbieten von AA oder AAA und ABA dagegen nicht."

Kapitel 2

Jedem Wort wird jetzt eine Farbe zugewiesen. Beispielhaft werden hier
Wörter der Länge 3 betrachtet. Die Anfangsbuchstaben der Wörter AA und
BA werden rot eingefärbt; die Anfangsbuchstaben der Wörter AB, AA und AB
blau. Eine Buchstabenfolge könnte dann folgendermaßen beginnen: Jeder
Buchstabe ist hier gemäß dem Wort der Länge 3 von dem er der
Anfangsbuchstabe ist eingefärbt: Das erste Wort der Länge 3 ist AAA,
also ist der erste Buchstabe rot. Das zweite Wort ist AAB, also ist der
zweite Buchstabe blau. Die letzten beiden Buchstaben lassen sich noch
nicht einfärben, da sich die Farbe immer erst aus den beiden
darauffolgenden Buchstaben ergibt.

Dass sich hier rote und blaue Buchstaben abwechseln ist kein Zufall,
sondern gerade das Ziel dieser Färbung. Die Frage, der
Kapitel 2 nachgeht, ist: Welche Wörter sollte man rot
und welche blau einfärben, damit man so ein alternierendes Farbmuster in
der Buchstabenfolge bekommt?

Für viele Buchstabenfolgen geht das überhaupt nicht. In einer, die mit
beginnt, werden die ersten beiden Buchstaben immer dieselbe Farbe haben.
Der Ausweg hier ist, das Wort AAAA zu verbieten. Genauso muss natürlich
das Wort BBBB verboten werden. Es zeigt sich, dass auch das nicht
reicht: Erst wenn man darüber hinaus die Wörter ABBA und BAAB verbietet,
lässt sich eine Lösung finden. Sie ist in der folgenden Tabelle 
dargestellt:

Rot eingefärbt Blau eingefärbt Verboten
---------------- ----------------- ----------
AAA AAB AAAA
ABA ABB ABBA
BAA BAB BAAB
BBA BBB BBBB

Eine eingefärbte Buchstabenfolge könnte dann folgendermaßen beginnen:

Man kann erkennen: Zwei Wörter der Länge 3, zwischen denen eine gerade
Zahl von Buchstaben steht, müssen immer verschiedene Farben haben. Steht
dagegen eine ungerade Zahl von Buchstaben zwischen ihnen, haben sie die
gleiche Farbe. Wenn ein Wort zweimal in der Buchstabenfolge vorkommt,
muss also auch eine ungerade Zahl an Buchstaben dazwischen stehen.
Ansonsten hätte dasselbe Wort erst die eine und später eine andere
Farbe.

Kapitel 1

Das gleichzeitige Verbieten der Wörter AAAA, ABBA, BAAB und BBBB
zerreißt die Buchstabenfolge nicht; alle Wörter der Länge 3 sind
weiterhin erlaubt und zwar in beliebiger Reihenfolge. Sie sind aber an
bestimmte Positionen gebunden. Ungewöhnlich dabei ist, dass Begrenzungen
bestehen bleiben, unabhängig davon, wie weit man in der Buchstabenfolge
geht.

Das Verbieten einiger Wörter führt häufig zu einem gewissen
Mindestabstand zwischen den Wörtern, die weiterhin erlaubt sind.
Verbietet man das Wort AAA zum Beispiel muss mindestens ein B zwischen
einem AA und dem nächsten AA stehen. Nach dem Mindestabstand aber kann
das Wort an beliebiger Stelle wieder auftreten. Das ist bei dem
Verbieten von AAAA, ABBA, BAAB und BBBB anders: Selbst wenn man nach
einem Auftreten des Wortes AAA 100 Schritte weiter geht, 1000 oder eine
Million: An der Stelle darf kein AAA stehen, schlicht weil 100, 1000 und
eine Million gerade Zahlen sind und zwischen einem AAA und dem nächsten
immer eine ungerade Zahl an Buchstaben stehen muss.

Vorgaben, die die Buchstabenfolge bis auf alle Ewigkeit strukturieren
werden genannt.

Wie viele Möglichkeiten gibt es, Durchmischung zu verhindern, ohne die
Buchstabenfolge zu zerreißen? Die Antwort wird in
Kapitel 1 gegeben: Nicht sehr viele. Wenn man die
Buchstabenfolge nicht zerreißt, wird in weniger als einem von 16 Fällen
Durchmischung verhindert.

• author: Garbe, Jonathan
• supervisor: Jörg Schmeling
• organization: Mathematics (Faculty of Engineering); Mathematics (Faculty of Sciences)
• alternative title: Observationer angående de Bruijn-grafer
• course: MATM01 20201
• year: 2020
• type: H2 - Master's Degree (Two Years)
• subject: Mathematics and Statistics
• keywords: de Bruijn graph, shift of finite type, symbolic dynamic, strongly connected graph, primitive graph, transitive shift, mixing shift, alternating colouring
• publication/series: Master’s Theses in Mathematical Sciences
• report number: LUNFMA-3118-2020
• ISSN: 1404-6342
• other publication id: 2020:E44
• language: English
• additional info: A popular scientific summary in English, Swedish and German can be found in appendix B.
• id: 9016243
• date added to LUP: 2020-07-07 14:34:48
• date last changed: 2020-07-07 14:34:48