Low-distortion embeddings of graphs with large girth (Q413201): Difference between revisions

This paper studies low-distortion embeddings of graphs with large girth. Recall that a map from a metric space \((X,d_{X})\) to a metric space \((Y,d_{Y})\) is said to be a \(C\)-bilipschitz embedding if there exists \(r>0\) such that, for all \(x,y\in X\) we have \(rd_{X}(u,v)\leq d_{Y}(f(u),f(v))\leq rCd_{X}(u,v)\). The smallest \(C\) for which such an \(r\) exists is the distortion of the map \(f\). We shall be interested in the case where the image space \(Y\) is \(\ell_{1}\) -- we will call this \(\ell_{1}\)-distortion. \(X\) will be a finite graph with the usual distance metric. The main result of the paper is to show that there exists a sequence of simple \(k\)-regular graphs, for \(k\geq 3\), which have indefinitely growing girths (recall girth is the length of the shortest cycle) and have uniformly bounded \(\ell_{1}\)-distortion. The rough idea of the construction is to start from a sequence of \(k\)-regular connected graphs \((G_{n})\) with indefinitely increasing girths \(g(G_{n})\) such that for some absolute constant \(\alpha>0\) we have \(g(G_{n})\geq \alpha d(G_{n})\) where \(d(G)\) denotes diameter of \(G\). Such sequences have been constructed in various pieces of earlier literature. The low distortion is guaranteed by thinking about lifts. Recall that a lift of graph \(G=(V,E)\) has vertex set \(V\times L\) for some finite set \(L\), and for each edge \(uv\) of \(G\) there is a perfect matching between the \(| L|\) vertices above \(u\) and the \(| L|\) vertices above \(v\). It is very easy to see that the lift \(\tilde{G}\) is still \(k\)-regular and easy to see that \(\tilde{G}\) has girth at least as large as \(G\). The low distortion is obtained by taking, for a graph \(G\) in the sequence, \(L\) to be the set \(\{0,1\}^{| E(G)|}\), so that elements of \(L\) are \(\{0,1\}\)-valued functions on \(E(G)\). We specify the perfect matching between the vertices above edge \(e\in E(G)\) by picking a bijection of \(L\), where the bijection corresponding to \(e\) maps every function \(f\) on \(E(G)\) to a function \(h\) which has the same value on every edge of \(G\) as \(f\) except on \(e\) where it takes the `opposite\'\, value to \(f\). These lifts are easily seen to be disconnected, so take a connected component in \(\tilde{G_{n}}\). With this choice, one can show that there is low distortion. The rough plan of the proof is to define a certain embedding of the graph into (eventually) \(\ell_{1}\) for each set of edges above an edge of \(G\). The main point is to estimate the distortion of this map (only its inverse is problematic) and this involves some careful bookkeeping of whether degrees in certain subgraphs are even or odd, and constructing certain paths in \(\tilde{G}\) whose length is bounded by a constant the number of edges repeated in the projection of the walk back down to \(G\). Implications in geometry and analysis are noted.