cybics/math/Cheeger constant.md

the tightest bottleneck of a graph: over all ways to cut the vertex set in two, the minimum ratio of edge boundary to the volume of the smaller side. small Cheeger constant means the graph has a thin waist; large means every region is well connected to the rest

it bounds the spectral gap from both sides (Cheeger inequality), so it controls how fast diffusion mixes and how fast focus converges on the cybergraph: a well-linked graph has no thin waist, a large gap, and geometric convergence of attention

perron-frobenius-theorem · spectral gap · Laplacian

Graph