Description
The Rado graph $R$ is a natural limit of the set of all finite graphs. One way to think of it is: on ${\mathbb N}$ (natural numbers) flip a fair coin for each pair of vertices and put an edge in if it comes up heads. Each vertex has infinite degree and the diameter is $2$. In joint work with Sourav Chatterjee and Laurent Miclo we study a natural laplacian: pick a positive probability $Q(j)$ on ${\mathbb N}$. From $i$, the walk chooses a nearest neighbor of $i$ (in $R$) with probability proportional to $Q(j)$.This walk has a stationary distribution and one may ask about rates of convergence to stationarity. The main result studies $Q(i) = 1/2^{(i+1)}$ and shows that, starting from $i$, $ {\rm log}^*_2 i$ steps suffice for convergence and, are needed for infinitely many $i$. The analysis uses a novel form of weighted Hardy inequalities for trees; Hardy’s inequalities with weights are familiar on ${\mathbb R}$ but even on ${\mathbb R}^{d}$ are a poorly developed tool. We develop the version on infinite trees and use it to get a spectral gap for the walk and to give a new picture of the geometry of the graph $R$. I will try to explain $R$ and Hardy’s inequalities (and the application) in ’mathematical English’. Understanding the problem for other $Q$ (eg $Q(j) = 1/j^2 $) is open.
