Pisot-Graph
In der Graphentheorie ist ein Pisot-Graph ein selbstähnlicher Graph, der mit Hilfe einer Pisot-Zahl definiert wird.
Definition
Gegeben sei eine Pisot-Zahl <math>\alpha>1</math>. Auf dem Folgenraum <math>\{0,1\}^{n}</math> wird eine Äquivalenzrelation mittels
- <math> s \sim t \iff \sum_{k=0}^{n-1}s_{k}\alpha^{-k}=\sum_{k=0}^{n-1}t_{k}\alpha^{-k}</math>
definiert.
Die Eckenmenge <math>V</math> des Pisot-Graphen ist durch <math> V=\bigcup_{n=1}^{\infty} V_{n}</math> gegeben, wobei <math>V_{n}=\{0,1\}^{n}/\sim</math> die Äquivalenzklassen der Relation <math>\sim</math> bezeichnet. Es gibt also maximal <math>2^n</math> Ecken in <math>V_n</math>, durch die Identifizierungen können es aber auch weniger Ecken sein.
Die Ecke <math>[s_{1},\dots,s_{n}]</math> wird mit <math>[s_{1},\dots,s_{n},0]</math> und <math>[s_{1},\dots,s_{n},1]</math> durch eine Kante verbunden, hierdurch ist die Kantenmenge <math>E</math> gegeben.
Beispiele
Der einfachste Pisot-Graph ist der Fibonacci-Graph, er ist durch den goldenen Schnitt <math>\alpha=\frac{1+\sqrt{5}}{2}</math> bestimmt, der die Gleichung <math>1=\alpha^{-1}+\alpha^{-2}</math> erfüllt. Aus dieser Gleichung ergibt sich, dass <math>(1,0,0)</math> mit <math>(0,1,1)</math> identifiziert wird, weshalb <math>V_3</math> in diesem Fall nur 7 Ecken hat.
Ähnlich wird (1,0,0,0) mit (0,1,1,0), (1,0,0,1) mit (0,1,1,1), (0,1,0,0) mit (0,0,1,1) und (1,1,0,0) mit (1,0,1,1) identifiziert, weshalb <math>V_4</math> in diesem Fall nur 12 Ecken hat.
Der Fibonacci-Graph kann auch als Cayley-Graph der Halbgruppe <math>G = \langle L,R|LRR=RLL\rangle</math> beschrieben werden.
Weitere Pisot-Graphen erhält man durch andere Pisot-Zahlen. Insbesondere ist der durch die Nullstelle von <math>x^3+x-1=0</math> bestimmte Graph nicht planar, siehe Abbildung.
Wachstumsrate
Die Wachstumsrate des Pisot-Graphen ist durch <math>W(\alpha)=\log\alpha</math> gegeben. Dies ist eine Konsequenz des klassischen Garsia-Lemmas.<ref>A.M. Garsia: Arithmetic properties of Bernoulli convolutions, Trans. Amer. Math. Soc. 162, 409–432, 1962, {{#invoke:Vorlage:Handle|f|scheme=doi|class=plainlinks|parProblem=Problem|errCat=Wikipedia:Vorlagenfehler/Parameter:DOI|errClasses=error editoronly|errHide=1|errNS=0 4 10 100}}.</ref>
Literatur
- J. Neunhäuserer: Random walks on infinite self-similar graphs. In: Electronic Journal of Probability, Band 12 (2007), Artikel 46, S. 1258–1275, {{#invoke:Vorlage:Handle|f|scheme=doi|class=plainlinks|parProblem=Problem|errCat=Wikipedia:Vorlagenfehler/Parameter:DOI|errClasses=error editoronly|errHide=1|errNS=0 4 10 100}}.
Weblinks
- Salem Numbers, Pisot Numbers, MahlerMeasure, and Graphs (PDF-Datei; 854 kB)
- J. Neunhäuserer: Random walks on infinite self-similar graphs.
Einzelnachweise
<references />