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 . Auf dem Folgenraum wird eine Äquivalenzrelation mittels
definiert.
Die Eckenmenge des Pisot-Graphen ist durch gegeben, wobei die Äquivalenzklassen der Relation bezeichnet. Es gibt also maximal Ecken in , durch die Identifizierungen können es aber auch weniger Ecken sein.
Die Ecke wird mit und durch eine Kante verbunden, hierdurch ist die Kantenmenge gegeben.
Beispiele
Der einfachste Pisot-Graph ist der Fibonacci-Graph, er ist durch den goldenen Schnitt bestimmt, der die Gleichung erfüllt. Aus dieser Gleichung ergibt sich, dass mit identifiziert wird, weshalb 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 in diesem Fall nur 12 Ecken hat.
Der Fibonacci-Graph kann auch als Cayley-Graph der Halbgruppe beschrieben werden.
Weitere Pisot-Graphen erhält man durch andere Pisot-Zahlen. Insbesondere ist der durch die Nullstelle von bestimmte Graph nicht planar, siehe Abbildung.
Wachstumsrate
Die Wachstumsrate des Pisot-Graphen ist durch 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
- J. Neunhäuserer: Random walks on infinite self-similar graphs.
- Salem Numbers, Pisot Numbers, MahlerMeasure, and Graphs (PDF-Datei; 854 kB)
Einzelnachweise
- ↑ A.M. Garsia: Arithmetic properties of Bernoulli convolutions, Trans. Amer. Math. Soc. 162, 409–432, 1962, doi:10.1090/S0002-9947-1962-0137961-5.
Auf dieser Seite verwendete Medien
Fibonacci-Graph