The logarithmic Sobolev constant of the lamplighter (Q1933623): Difference between revisions

A lamplighter graph \(G^*\) is constructed from a finite graph \(G=(V, E)\) with \(n\) vertices by associating with each vertex \(x\) in \(V\) a lamp that can be on or off as specified by a binary \(n\)-sequence \(s\). The vertex set of \(G^*\) consists of all pairs \((s, x)\) of sequences and vertices in \(G\). Any two such pairs \((s, x)\) and \((s^*, x^*)\) are adjacent in \(G^*\) if either (1) \(s=s^*\) and \(x\) is adjacent to \(x^*\) or (2) \(s(y)=s^*(y)\) for all \(y\) different from \(x\) and \(x=x^*\). For a random walk in \(G\) by a lamplighter, the first case corresponds to a move from \(x\) to \(x^*\) without changing any lights, and the second case corresponds to staying at \(x\) and randomly possibly changing the light only at that site \(x\). The convergence properties of the random walk and the lighting processes are studied by estimating the logarithmic Sobolev constant of \(G^*\). The results are illustrated by considering the torus, the regular tree, the complete graph and the hypercube.