Compressions and isoperimetric inequalities (Q807642): Difference between revisions

Let \(G=(V,E)\) be a graph. For \(A\subset V\) and \(y\in V\), set \(D(A,y)=\inf \{d(x,y):\) \(x\in A\}\), where d is the usual graph metric. For \(t=0,1,2,...\), \(A_{(t)}=\{y\in V:\) d(A,y)\(\leq t\}\) is the t-boundary of A and \(A_{(1)}=\partial A\) is the boundary of A. \(Z^ n_+\) is viewed as a graph on \(V=Z^ n_+=\{x\in Z^ n:\) \(x_ i\geq 0\) for all \(i\}\) in which x is adjacent to y if for some i, \(| x_ i-y_ i| =1\) and \(x_ j=y_ j\) for all \(j\neq i\). This is the infinite grid, the Cartesian product of infinite paths \(Z_+\). \([k]^ n\) is the Cartesian product of n paths [k] on \(V=[k]=\{0,1,...,k-1\}\) with i adjacent to i-1 for \(1\leq i\leq k-1\). The simplicial order on \(Z^ n_+\) is given by: \(x<y\) if either \(\Sigma x_ i<\Sigma y_ i\), or \(\Sigma x_ i=\Sigma y_ i\) and for some j, \(x_ j>y_ j\) and for all \(i<j\), \(x_ i=y_ i\). Only finite subsets A of \(Z^ n_+\) are considered. For \(m=0,1,...\), \(\partial^ n(m)\) denotes the size of the boundary of the first m points of \(Z^ n_+\) in the simplicial order. The restriction of the above order to \([k]^ n\) provides it with its simplicial order. Similar terminology is adopted for this. In the first part the authors prove \[ (1)\text{ for } finite\quad A\subset Z^ n_+,\quad | \partial A| \geq \partial^{(n)}(| A|), \] \[ (2)\text{ for } A\subset [k]^ n,\quad | \partial A| \geq \partial_ k^{(n)}(| A|). \] The first is a result due to \textit{D. L. Wang} and \textit{P. Wang} [Discrete isoperimetric problems, SIAM J. Appl. Math. 32, 860-870 (1977; Zbl 0362.05047)]. The proof technique employed is compression of a set. Roughly speaking, for a coordinate direction i, the i-compression of a set A replaces it by an equinumerous set \(C_ i(A)\) which is `convex' (`regular') without gaps in the i-direction, and `touches' the i-th coordinate plane. The i-direction can be replaced by any vector direction. For a graph G of diameter D and given \(\epsilon\), \(0<\epsilon <1\), let \(\alpha (G,\epsilon)=\min \{1-| A_{(\epsilon D)}| /| V|:\;A\subset V,\quad | A| /| V| \geq \}.\) Then a family \((G_ n)_ 1^{\infty}\) of graphs is a normal Levy family if there are constants \(c_ 1,c_ 2>0\) such that \(\alpha (G_ n,\epsilon)\leq c_ 1e^{-c_ 2\epsilon^ 2n}\) for all n and \(\epsilon\). In the second part, the authors extend inequality (2) to a finite product of arbitrary graphs and deduce therefrom that \((G_ n)\) is a normal Levy family with \(c_ 2=6D^ 2/(k^ 2-1)\), for a connected graph G with diameter D and order k. This improves a result of \textit{N. Alon} and \textit{V. D. Milman} \([\lambda_ 1\), isoperimeric inequalities, and superconcentrators, J. Comp. Theory. Ser. B 38, 73-88 (1985; Zbl 0549.05051)]. Let \(X^{(r)}=\{1,2,...,n\}^ r\) and let \({\mathcal A}\) be a set system on \(X^{(r)}\). The (lower) shadow of \({\mathcal A}\) is \(\partial^-{\mathcal A}=\{B\subset X^{(r-1)}:\;B\subset A\text{ for some } A\in {\mathcal A}\}.\) The colex order on \(X^{(r)}\) is given by \(A<B\) if max(A\(\Delta\) B)\(\in B\). Let \({\mathcal J}\) denote the set of the first \(| {\mathcal A}|\) elements in the colex order on \(X^{(r)}\). In the final part, the authors give a direct, short proof of the following theorem of Kruskal and Katona using an extended notion of compression \[ (3)\quad | \partial^-{\mathcal A}| \geq | \partial^-{\mathcal J}|. \]