Pisot-Graph

In d​er Graphentheorie i​st ein Pisot-Graph e​in selbstähnlicher Graph, d​er mit Hilfe e​iner Pisot-Zahl definiert wird.

Definition

Gegeben sei eine Pisot-Zahl ${\displaystyle \alpha >1}$. Auf dem Folgenraum ${\displaystyle \{0,1\}^{n}}$ wird eine Äquivalenzrelation mittels

${\displaystyle s\sim t\iff \sum _{k=0}^{n-1}s_{k}\alpha ^{-k}=\sum _{k=0}^{n-1}t_{k}\alpha ^{-k}}$

definiert.

Die Eckenmenge ${\displaystyle V}$ des Pisot-Graphen ist durch ${\displaystyle V=\bigcup _{n=1}^{\infty }V_{n}}$ gegeben, wobei ${\displaystyle V_{n}=\{0,1\}^{n}/\sim }$ die Äquivalenzklassen der Relation ${\displaystyle \sim }$ bezeichnet. Es gibt also maximal ${\displaystyle 2^{n}}$ Ecken in ${\displaystyle V_{n}}$, durch die Identifizierungen können es aber auch weniger Ecken sein.

Die Ecke ${\displaystyle [s_{1},\dots ,s_{n}]}$ wird mit ${\displaystyle [s_{1},\dots ,s_{n},0]}$ und ${\displaystyle [s_{1},\dots ,s_{n},1]}$ durch eine Kante verbunden, hierdurch ist die Kantenmenge ${\displaystyle E}$ gegeben.

Beispiele

Fibonacci-Graph

Der einfachste Pisot-Graph ist der Fibonacci-Graph, er ist durch den goldenen Schnitt ${\displaystyle \alpha ={\frac {1+{\sqrt {5}}}{2}}}$ bestimmt, der die Gleichung ${\displaystyle 1=\alpha ^{-1}+\alpha ^{-2}}$ erfüllt. Aus dieser Gleichung ergibt sich, dass ${\displaystyle (1,0,0)}$ mit ${\displaystyle (0,1,1)}$ identifiziert wird, weshalb ${\displaystyle V_{3}}$ 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 ${\displaystyle V_{4}}$ in diesem Fall nur 12 Ecken hat.

Der Fibonacci-Graph kann auch als Cayley-Graph der Halbgruppe ${\displaystyle G=\langle L,R|LRR=RLL\rangle }$ beschrieben werden.

Weitere Pisot-Graphen erhält man durch andere Pisot-Zahlen. Insbesondere ist der durch die Nullstelle von ${\displaystyle x^{3}+x-1=0}$ bestimmte Graph nicht planar, siehe Abbildung.

Ein nicht planarer Pisot-Graph

Wachstumsrate

Die Wachstumsrate des Pisot-Graphen ist durch ${\displaystyle W(\alpha )=\log \alpha }$ gegeben. Dies ist eine Konsequenz des klassischen Garsia-Lemmas.[1]

Literatur

• J. Neunhäuserer: Random walks on infinite self-similar graphs. In: Electronic Journal of Probability, Band 12 (2007), Artikel 46, S. 1258–1275, doi:10.1214/EJP.v12-448.

Weblinks

• Salem Numbers, Pisot Numbers, MahlerMeasure, and Graphs (PDF-Datei; 854 kB)
• J. Neunhäuserer: Random walks on infinite self-similar graphs.

Einzelnachweise

1. A.M. Garsia: Arithmetic properties of Bernoulli convolutions, Trans. Amer. Math. Soc. 162, 409–432, 1962, doi:10.1090/S0002-9947-1962-0137961-5.