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

Bolla, Marianna; Molnár-Sáska, Gábor

Discrete Math. 282, No. 1-3, 23-33 (2004).

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.

Reviewer: Dragan Stevanović (Niš)

MSC:

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

Keywords:

weighted Laplacian; Cheeger constant of hypergraphs; symmetric maximal correlation; conditional probability estimation

References:

[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