Exact Sgtcheegerbound constant, with the eigenvalue bounds it satisfies

Computed by exhaustive enumeration of the vertex bipartitions, so it is exact rather than a relaxation. Enumeration is exponential, hence the max_n guard.

Usage

Sgtcheegerbound(W, max_n = 20)

Arguments

W

Symmetric non-negative weight matrix, connected.

max_n

Refuse to enumerate beyond this many vertices.

Value

List with h, argmin, cut, vol_S, vol_complement, lambda1, upper_bound, lower_bound, lower_bound_sharp, n.

Details

Formula: h_G(S) = |E(S, Sbar)| / min(vol S, vol Sbar), h_G = min_S h_G(S); Sgtcheegerbound inequality 2 h_G >= lambda_1 > h_G^2 / 2, and the sharper lambda_1 >= 1 - sqrt(1 - h_G^2)

References

Chung (1997), Spectral Graph Theory, CBMS 92, Section 2.2, equations (2.1) and (2.2) for h_G(S) and h_G; Theorem 2.2 for 2 h_G >= lambda_1 > h_G^2 / 2; Theorem 2.3 for lambda_1 >= 1 - sqrt(1 - h_G^2).

Examples

W <- matrix(1, 4, 4); diag(W) <- 0; W[1, 4] <- W[4, 1] <- 0
Sgtcheegerbound(W)$h
#> [1] 0.6