Pisot graph

In graph theory , a pisot graph is a self-similar graph that is defined using a pisot number .

definition

Given a pisot number . An equivalence relation is established on the sequence space by means of ${\ displaystyle \ alpha> 1}$ ${\ displaystyle \ {0.1 \} ^ {n}}$

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

Are defined.

The vertex set of the Pisot graph is given by, where denotes the equivalence classes of the relation . So there are at most corners in , but due to the identifications there can also be fewer corners. ${\ displaystyle V}$ ${\ displaystyle V = \ bigcup _ {n = 1} ^ {\ infty} V_ {n}}$ ${\ displaystyle V_ {n} = \ {0.1 \} ^ {n} / \ sim}$ ${\ displaystyle \ sim}$ ${\ displaystyle 2 ^ {n}}$ ${\ displaystyle V_ {n}}$

The corner is connected with and by an edge, this gives the number of edges . ${\ displaystyle [s_ {1}, \ dots, s_ {n}]}$ ${\ displaystyle [s_ {1}, \ dots, s_ {n}, 0]}$ ${\ displaystyle [s_ {1}, \ dots, s_ {n}, 1]}$ ${\ displaystyle E}$

Examples

Fibonacci graph

The simplest Pisot graph is the Fibonacci graph, it is determined by the golden ratio that satisfies the equation . This equation shows that with is identified, which is why in this case it has only 7 corners. ${\ displaystyle \ alpha = {\ frac {1 + {\ sqrt {5}}} {2}}}$ ${\ displaystyle 1 = \ alpha ^ {- 1} + \ alpha ^ {- 2}}$ ${\ displaystyle (1,0,0)}$ ${\ displaystyle (0,1,1)}$ ${\ displaystyle V_ {3}}$

Similarly, (1,0,0,0) becomes with (0,1,1,0), (1,0,0,1) with (0,1,1,1), (0,1,0,0 ) is identified with (0,0,1,1) and (1,1,0,0) with (1,0,1,1), which is why in this case it has only 12 vertices. ${\ displaystyle V_ {4}}$

The Fibonacci graph can also be described as the Cayley graph of the semigroup . ${\ displaystyle G = \ langle L, R | LRR = RLL \ rangle}$

Other pisot graphs can be obtained from other pisot numbers . In particular, the graph determined by the zero of is not planar, see figure. ${\ displaystyle x ^ {3} + x-1 = 0}$

A non-planar pisot graph

Growth rate

The growth rate of the Pisot graph is given by. This is a consequence of the classical Garsia lemma. ${\ displaystyle W (\ alpha) = \ log \ alpha}$

literature

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

Web links

Individual evidence

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

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