Optimization problems for weighted graphs and related correlation estimates. (English) Zbl 1047.05026

Authors’ abstract: \(L_2\) and \(L_1\)-norm optimization problems for weighted graphs are discussed and compared in the paper. In the setting where the standardized weight matrix \(W\) is regarded as a joint probability distribution \(D\) of two discrete random variables with equal marginals, the refined upper bound of \(\sqrt{\lambda_1(2-\lambda_1)}\) for the Cheeger constant gives the relation \[ \frac{1-\rho_1}2\leq \min_{B\subset{\mathbb R}} P_W(X'\in\overline B| X\in B)\leq \sqrt{1-\rho_1^2}, \] where \(B\) is a Borel set, \(P_D(X\in B)\leq 1/2\), \(X,X'\) i.d., with the symmetric maximal correlation \(\rho_1\), provided that it is positive, or equivalently, for the smallest positive eigenvalue of the weighted Laplacian \(\lambda_1\leq 1\) holds.


05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
60C05 Combinatorial probability
62H20 Measures of association (correlation, canonical correlation, etc.)
Full Text: DOI


[1] Alon, N.; Milman, V.D., λ1, isoperimetric inequalities for graphs and superconcentrators, J. combin. theory B, 38, 73-88, (1985) · Zbl 0549.05051
[2] Bolla, M., Singular values decomposition of linear operators on Hilbert-spaces, Alkalmazott mat. lapok, 13, 189-206, (1987 88), (in Hungarian)
[3] Bolla, M., Correspondence analysis, Alkalmazott mat. lapok, 13, 207-230, (1987 88), (in Hungarian)
[4] Bolla, M., Spectra, Euclidean representations and clusterings of hypergraphs, Discrete math., 117, 19-39, (1993) · Zbl 0781.05036
[5] Bolla, M.; Tusnády, G., Spectra and optimal partitions of weighted graphs, Discrete math., 128, 1-20, (1994) · Zbl 0796.05066
[6] Breiman, L.; Friedman, H.J., Estimating optimal transformations for multiple regression and correlation, J. amer. statist. assoc., 80, 580-619, (1985) · Zbl 0594.62044
[7] Buser, P., On the bipartition of graphs, Discrete appl. math., 9, 105-109, (1984) · Zbl 0544.05038
[8] Cheeger, J., A lower bound for the smallest eigenvalue of the Laplacian, (), 195-199 · Zbl 0212.44903
[9] Chung, F.R.K., Spectral graph theory, CBMS regional conference series in mathematics, Vol. 92, (1994), AMS Publications Providence, RI · Zbl 0872.05052
[10] Diaconis, P.; Stroock, D.W., Geometric bounds for eigenvalues of Markov chains, Ann. appl. probab., 1, 36-61, (1991) · Zbl 0731.60061
[11] A. Lubotzky, Discrete groups, expanding graphs, and invariant measures, Appendix by J.D. Rogawski, Progress in Mathematics, Vol. 125, Birkhäuser, Basel, Boston, Berlin, 1994. · Zbl 0826.22012
[12] Mohar, B., Isoperimetric numbers of graphs, J. combin. theory B, 47, 274-291, (1989) · Zbl 0719.05042
[13] Papadimitriou, C.H.; Raghavan, P.; Tamaki, H.; Vempala, S., Latent semantic indexinga probabilistic analysis, J. comput. system sci., 61, 217-235, (2000) · Zbl 0963.68063
[14] Rényi, A., On measures of dependence, Acta math. acad. sci. hung., 10, 441-451, (1959) · Zbl 0091.14403
[15] Sinclair, A.; Jerrum, M., Approximate counting, uniform generation and rapidly mixing Markov chains, Inform. and comput., 82, 93-133, (1989) · Zbl 0668.05060
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.