×

Compressions and isoperimetric inequalities. (English) Zbl 0731.05043

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 D. L. Wang and 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 N. Alon and 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}|. \]

MSC:

05C99 Graph theory
05C38 Paths and cycles
52B60 Isoperimetric problems for polytopes
05C12 Distance in graphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alon, N.; Milman, V. D., \(λ_1\), isoperimetric inequalities for graphs, and superconcentrators, J. Combin. Theory Ser. B, 38, 73-88 (1985) · Zbl 0549.05051
[2] Azuma, K., Weighted sums of certain dependent random variables, Tôhoku Math. J., 19, 357-367 (1967) · Zbl 0178.21103
[3] Bollobás, B., Combinatorics, ((1986), Cambridge Univ. Press: Cambridge Univ. Press London/New York), xii-177 · Zbl 0595.05001
[4] Clements, G. F.; Lindström, B., A generalisation of a combinatorial theorem of Macaulay, J. Combin. Theory, 7, 230-238 (1969) · Zbl 0186.01704
[5] Daykin, D. E., A simple proof of the Kruskal-Katona theorem, J. Combin. Theory Ser. A, 17, 252-253 (1974) · Zbl 0287.05004
[6] Frankl, P., A new short proof of the Kruskal-Katona theorem, Discrete Math., 48, 327-329 (1984) · Zbl 0539.05006
[7] Frankl, P.; Füredi, Z., A short proof for a theorem of Harper about Hamming spheres, Discrete Math., 34, 311-313 (1981) · Zbl 0482.05002
[8] Gromov, M.; Milman, V. D., A topological application of the isoperimetric inequality, Amer. J. Math., 105, 843-854 (1983) · Zbl 0522.53039
[9] Harper, L. H., Optimal numberings and isoperimetric problems on graphs, J. Combin. Theory, 1, 385-393 (1966) · Zbl 0158.20802
[10] Katona, G. O.H, A theorem on finite sets, (Erdős, P.; Katona, G. O.H, Theory of Graphs (1968), Akadémiai Kiadó: Akadémiai Kiadó Budapest), 187-207 · Zbl 0878.05079
[11] Kruskal, J. B., The number of simplices in a complex, (Mathematical Optimization Techniques (1963), Univ. of California Press: Univ. of California Press Berkeley), 251-278 · Zbl 0116.35102
[12] Maurey, B., Espaces de Banach: construction de suites symétriques, CRAS Paris Sér. A-B, 288, 679-681 (1979) · Zbl 0398.46019
[13] Milman, V. D.; Schechtman, G., Asymptotic theory of finite dimensional normed spaces, (Lecture Notes in Mathematics, Vol. 1200 (1986), Springer-Verlag), viii-156 · Zbl 0911.52002
[14] Schechtman, G., Lévy type inequality for a class of finite metric spaces, (Chao, J.-A; Woyczyński, W. A., Martingale Theory in Harmonic Analysis and Banach Spaces. Martingale Theory in Harmonic Analysis and Banach Spaces, Lecture Notes in Mathematics, Vol. 939 (1982), Springer-Verlag), 211-215 · Zbl 0512.46010
[15] Wang, D.-L; Wang, P., Discrete isoperimetric problems, SIAM J. Appl. Math., 32, 860-870 (1977) · Zbl 0362.05047
[16] Wang, D.-L; Wang, P., Extremal configurations on a discrete torus and a generalization of the generalized Macaulay theorem, SIAM J. Appl. Math., 33, 55-59 (1977) · Zbl 0362.05048
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.