Edge isoperimetric inequalities for product graphs (Q1970722)

Let \({\mathcal F}\) be a function such that \(|\partial\Omega|> {\mathcal F}(|\Omega|)\) for every nonempty subset \(\Omega\) of \(V(G)\), where \(\partial\Omega\) denotes the set of edges of the graph connecting vertices of \(\Omega\) with the complement \(V\setminus\Omega\). Then \({\mathcal F}\) is called an edge-isoperimetric inequality and \(\partial\Omega\) is named the boundary of \(\Omega\). The author obtains such inequalities which are sharp for certain types of subsets called isoperimetric sets (sets of given size which have the smallest edge-boundary). Using a simple equivalence between isoperimetric inequalities and certain analytic inequalities in Riemannian manifolds [\textit{O. S. Rothaus}, J. Funct. Anal. 64, 296-313 (1985; Zbl 0578.46028)], the author proves the following theorem for product graphs: Let \(\ell(G)\) be the minimum of \(|\partial\Omega|/ |\Omega|\ln(|V|/ |\Omega|)\) over all nonempty subsets \(\Omega\) of \(V(G)\). Then \(\ell(G)= \ell(G^n)\) for any Cartesian power \(G^n\).