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

Fibonacci-Graph

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.

Ein nicht planarer Pisot-Graph

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

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.

Auf dieser Seite verwendete Medien

Fibonacci-Graph.png
Fibonacci-Graph