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 $\alpha >1$. Auf dem Folgenraum $\{0,1\}^{n}$ wird eine Äquivalenzrelation mittels

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

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

Beispiele

Fibonacci-Graph

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

Der Fibonacci-Graph kann auch als Cayley-Graph der Halbgruppe $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 $x^{3}+x-1=0$ bestimmte Graph nicht planar, siehe Abbildung.

Ein nicht planarer Pisot-Graph

Wachstumsrate

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

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.