Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Cheeger inequality — where it appears

The bracket lambda2/2 <= phi <= sqrt(2 lambda2) relating a graph's normalised second eigenvalue to its best conductance. The lower half is attained on the complete graph; the upper half is loosest on graphs with a real bottleneck.

Named by 2 essays across one field — each of them below, with the objects they name alongside it.

Also named here as relaxation — the same set of essays touches all of them, so they are one junction rather than several.

0481216202410⁻²10⁻¹1vertices on the smaller sideconductance of the prefix cut0.00752, the best prefixthe rounding stepλ₂0.14cuts considered23best conductance0.0075at k =12worst prefix1the dashed curve is the eigenvectorthe solid one is what it costs

The vector that has to be rounded

A spectral partition is an eigenvector, and an eigenvector is a real vector. The answer wanted is a subset. Something has to turn one into the other, and the something is a heuristic applied after the linear algebra has finished.

graph · spectral partition 10⁻³10⁻²10⁻¹110¹12345678910conductance, and the two bounds on itpathcyclegridbarbelltwo blockshypercubepreferentialstarcompletethe bar is the inequalitythe dot is the graph

A bound with a square root in it

Cheeger's inequality brackets a graph's best cut between λ₂/2 and √(2λ₂). The lower bound is attained exactly. The upper one is loose by a factor of fourteen — on the one graph in the census with a real bottleneck, which is the shape it is always quoted about.

graph · spectral partition

Named alongside it

The objects these essays reach for when they reach for this one.

Algebraic connectivityConductanceFiedler vectorRelaxationSpectral partitionBound tightnessCombinatorial optimumGraph automorphismNormalised laplacianRank is a decisionSweep cut

All concepts