Vertical perimeter versus horizontal perimeter (Q1643390): Difference between revisions

The topic of this paper arose as a way to approach one of the fundamental problems in Computer Science: find the most efficient (polynomial) approximation algorithm for the sparsest cut problem. (The problem itself is known to be NP-hard, see [\textit{F. Shahrokhi} and \textit{D. W. Matula}, J. Assoc. Comput. Mach. 37, No. 2, 318--334 (1990; Zbl 0696.68071)]). The Goemans-Linial semidefinite approximation algorithm, see [\textit{M. X. Goemans}, Math. Program. 79, No. 1--3 (B), 143--161 (1997; Zbl 0887.90139)], which is asymptotically the best known at the moment, has approximation ratio \(\rho_{\mathrm{GL}}(n)\) (for problems of size \(n\)) equal to the supremum of the \(L_1\)-distortion over all \(n\)-point metric spaces of negative type. The estimate of this distortion from below is the main goal of the present paper. One of the main results of the paper (Theorem 5): For every integer \(n\geq 2\), there is an absolute constant \(c>0\) such that \(c\sqrt{\log n}\leq\rho_{\mathrm{GL}}(n)\leq (\log n)^{\frac12+o(1)}\). Only the leftmost inequality is proved in the paper, the rightmost inequality was proved in [\textit{S. Arora} et al., J. Am. Math. Soc. 21, No. 1, 1--21 (2008; Zbl 1132.68070)]. The proof of the leftmost inequality uses the approach suggested by \textit{J. R. Lee} and \textit{A. Naor} [``\(L_p\) metrics on the Heisenberg group and the Goemans-Linial conjecture'', in: Proceedings of 47th annual IEEE Symposium on Foundations of Computer Science. Los Alamitos, CA: IEEE Computer Society. 99--108 (2006; \url{doi:10.1109/focs.2006.47})], namely, the observation that Heisenberg groups admit equivalent metrics of negative type and therefore lower estimates for \(\rho_{\mathrm{GL}}(n)\) can be obtained by studying the \(L_1\)-distortions of finite subsets of Heisenberg groups. It should be mentioned that \textit{J. Cheeger} et al. [Acta Math. 207, No. 2, 291--373 (2011; Zbl 1247.46020)] proved that \(\rho_{\mathrm{GL}}(n)\geq c (\log n)^\delta\) for some absolute constants \(\delta, c>0\). The goal of the present paper is to get the maximal possible exponent \(\delta=\frac12\). In fact, the upper and lower bounds in Theorem 5 coincide up to lower-order factors. Theorem 5 in the paper is derived from the result stated below (Theorem 3) on Heisenberg groups which the authors call ``vertical versus horizontal isoperimetric inequality''. It is important to mention that the Heisenberg groups studied in this paper can be regarded as high-dimensional generalizations of what is called the Heisenberg group in many sources. We reproduce the description from the authors' abstract: ``Given \(k\in \mathbb{N}\), the \(k\)-th discrete Heisenberg group, denoted by \(\mathbb{H}_{\mathbb{Z}}^{2k+1}\), is the group generated by the elements \(a_1,b_1,\dots,a_k,b_k,c\), subject to the commutator relations \([a_1,b_1]=\ldots=[a_k,b_k]=c\), while all the other pairs of elements from this generating set are required to commute, i.e., for every distinct \(i,j\in \{1,\dots,k\}\), we have \([a_i,a_j]=[b_i,b_j]=[a_i,b_j]=[a_i,c]=[b_i,c]=1\) (in particular, this implies that \(c\) is in the center of \(\mathbb{H}_{\mathbb{Z}}^{2k+1}\)). Denote \(\mathfrak{S}_k=\{a_1,b_1,a_1^{-1},b_1^{-1},\ldots,a_k,b_k,a_k^{-1},b_k^{-1}\}\). The horizontal boundary of \(\Omega\subset \mathbb{H}_{\mathbb{Z}}^{2k+1}\), denoted by \(\partial_{\mathrm h}\Omega\), is the set of all those pairs \((x,y)\in \Omega\times (\mathbb{H}_{\mathbb{Z}}^{2k+1}\setminus \Omega)\) such that \(x^{-1}y\in \mathfrak{S}_k\). The horizontal perimeter of \(\Omega\) is the cardinality \(|\partial_{\mathrm h}\Omega|\) of \(\partial_{\mathrm h}\Omega\), i.e., it is the total number of edges incident to \(\Omega\) in the Cayley graph induced by \(\mathfrak{S}_k\). For \(t\in \mathbb{N}\), define \(\partial^t_{\mathrm v} \Omega\) to be the set of all those pairs \((x,y)\in \Omega\times (\mathbb{H}_{\mathbb{Z}}^{2k+1}\setminus \Omega)\) such that \(x^{-1}y\in \{c^t,c^{-t}\}\). Thus, \(|\partial^t_{\mathrm v}\Omega|\) is the total number of edges incident to \(\Omega\) in the (disconnected) Cayley graph induced by \(\{c^t,c^{-t}\}\subset \mathbb{H}_{\mathbb{Z}}^{2k+1}\). The vertical perimeter of \(\Omega\) is defined by \(|\partial_{\mathrm v}\Omega|= \sqrt{\sum_{t=1}^\infty |\partial^t_{\mathrm v}\Omega|^2/t^2}\).'' The authors prove (Theorem 3) that, if \(k\geq 2\), then \(|\partial_{\mathrm v}\Omega|\leq \frac{C}{k} |\partial_{\mathrm h}\Omega|\) for some absolute constant \(C\). They emphasize that, for \(k=1\), the results are different; these results will be presented in a separate paper whose short description is provided in an `Added in proof' note. The proof of these very impressive results contains many sophisticated steps and cannot be outlined here. I refer the readers to the `Roadmap' on pages 185--186 of the paper, I would only like to mention that the proof of Theorem 3 takes place in a setting of `continuous' Heisenberg groups.