imported>No identd: 1 EMIS Link repariert (davor 404, weil EMIS wanderte? idqk) & 2 auf HTTPS korrigiert; keine weiteren Änderungen/Angleichungen, obwohl die References wohl mehr Pflege verdient hätten — leider keine Zeit

2023-04-29T15:11:13Z

1 EMIS Link repariert (davor 404, weil EMIS wanderte? idqk) & 2 auf HTTPS korrigiert; keine weiteren Änderungen/Angleichungen, obwohl die References wohl mehr Pflege verdient hätten — leider keine Zeit

Neue Seite

In der [[Graphentheorie]] ist ein '''Pisot-Graph''' ein [[selbstähnlich]]er [[Graph (Graphentheorie)|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 ==
[[Datei:Fibonacci-Graph.png|miniatur|Fibonacci-Graph]]
Der einfachste Pisot-Graph ist der Fibonacci-Graph, er ist durch den [[goldener Schnitt|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-Zahl]]en. Insbesondere ist der durch die Nullstelle von <math>x^3+x-1=0</math> bestimmte Graph nicht planar, siehe Abbildung.
[[Datei:Pisotmin.svg|miniatur|Ein nicht planarer Pisot-Graph]]

== Wachstumsrate ==
Die [[Wachstum von Graphen|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, {{DOI|10.1090/S0002-9947-1962-0137961-5}}.</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, {{DOI|10.1214/EJP.v12-448}}.

== Weblinks ==
* [https://www.emis.de/journals/EM/expmath/volumes/14/14.2/McKee.pdf Salem Numbers, Pisot Numbers, MahlerMeasure, and Graphs] (PDF-Datei; 854 kB)
* [https://www.emis.de/journals/EJP-ECP/_ejpecp/include/getdocd383.pdf?id=4108&article=1736&mode=pdf J. Neunhäuserer: ''Random walks on infinite self-similar graphs''.]

== Einzelnachweise ==
<references />

[[Kategorie:Graphenklasse]]

Pisot-Graph - Versionsgeschichte

imported>No identd: 1 EMIS Link repariert (davor 404, weil EMIS wanderte? idqk) & 2 auf HTTPS korrigiert; keine weiteren Änderungen/Angleichungen, obwohl die References wohl mehr Pflege verdient hätten — leider keine Zeit