Optimization problems for weighted graphs and related correlation estimates Original Research Article

L2- and L1-norm optimization problems for weighted graphs are discussed and compared in the paper. The standardized weight matrix W is also regarded as a joint probability distribution of two discrete random variables with equal marginals, D. In this setting, the refined upper bound λ1(2−λ1) for the Cheeger constant gives the relation1−ρ12⩽minB⊂R Borel-setPD(X∈B)⩽1/2X,X′ i.d. PW(X′∈B̄|X∈B)⩽1−ρ12with the symmetric maximal correlation ρ1, provided that it is positive, or equivalently, for the smallest positive eigenvalue of the weighted Laplacian λ1⩽1 holds.