graph-picture
At its defaults it draws two blocks 40: 40 vertices, 223 edges, and a matrix built from them. The two blocks 40 laid out at its own second and third Laplacian eigenvectors, so the picture is the same object the measurements are about. The Laplacian L = D − A is built by subtraction of integers, so every row sums to exactly zero — measured at 0, not at the rounding level — and L·1 is the zero vector with no arithmetic error anywhere in it. Its 1 zero eigenvalue counts the connected components, which breadth-first search also puts at 1; the smallest non-zero eigenvalue is 1.458 and the largest computed zero is 4.26·10⁻¹⁶, a gap of 3.42·10¹⁵. The quadratic form xᵀLx is Σ over edges of (xᵢ − xⱼ)², which at the alternating vector is 444.
graph-picture is one function in lib/figures/graphlap.js —
the matrix a graph makes — row sums that are exactly zero, a count that is a threshold, and a partition with no vector. Everything below came out of it during this build, at
arguments taken from the essays rather than invented for this page. A figure here is the
figure a reader meets in an essay, and if the generator changes, this page changes with it.
At its defaults
Drawn even though every essay passes arguments — which on this site is every essay, at 100% of placements since the standard pass. A default nothing exercises is a trap for the next essay to call this with none, and this is the page where a default that has drifted from the figures around it becomes visible.
The two blocks 40 laid out at its own second and third Laplacian eigenvectors, so the picture is the same object the measurements are about. The Laplacian L = D − A is built by subtraction of integers, so every row sums to exactly zero — measured at 0, not at the rounding level — and L·1 is the zero vector with no arithmetic error anywhere in it. Its 1 zero eigenvalue counts the connected components, which breadth-first search also puts at 1; the smallest non-zero eigenvalue is 1.458 and the largest computed zero is 4.26·10⁻¹⁶, a gap of 3.42·10¹⁵. The quadratic form xᵀLx is Σ over edges of (xᵢ − xⱼ)², which at the alternating vector is 444.
family: "barbell", n: 24
The arguments are the ones A bound with a square root in it passes. A value drawn at the generator's defaults instead would be a picture no essay asked for and no assertion has been run against.
The barbell 12 laid out at its own second and third Laplacian eigenvectors, so the picture is the same object the measurements are about. The Laplacian L = D − A is built by subtraction of integers, so every row sums to exactly zero — measured at 0, not at the rounding level — and L·1 is the zero vector with no arithmetic error anywhere in it. Its 1 zero eigenvalue counts the connected components, which breadth-first search also puts at 1; the smallest non-zero eigenvalue is 0.1443 and the largest computed zero is 8.24·10⁻¹⁶, a gap of 1.75·10¹⁴. The quadratic form xᵀLx is Σ over edges of (xᵢ − xⱼ)², which at the alternating vector is 292.
family: "complete", n: 20
The arguments are the ones A bound with a square root in it passes. A value drawn at the generator's defaults instead would be a picture no essay asked for and no assertion has been run against.
The complete 20 laid out at its own second and third Laplacian eigenvectors, so the picture is the same object the measurements are about. The Laplacian L = D − A is built by subtraction of integers, so every row sums to exactly zero — measured at 0, not at the rounding level — and L·1 is the zero vector with no arithmetic error anywhere in it. Its 1 zero eigenvalue counts the connected components, which breadth-first search also puts at 1; the smallest non-zero eigenvalue is 20 and the largest computed zero is 7.22·10⁻¹⁶, a gap of 2.77·10¹⁶. The quadratic form xᵀLx is Σ over edges of (xᵢ − xⱼ)², which at the alternating vector is 400.
family: "hypercube", n: 32
The arguments are the ones A bound with a square root in it passes. A value drawn at the generator's defaults instead would be a picture no essay asked for and no assertion has been run against.
The hypercube 5 laid out at its own second and third Laplacian eigenvectors, so the picture is the same object the measurements are about. The Laplacian L = D − A is built by subtraction of integers, so every row sums to exactly zero — measured at 0, not at the rounding level — and L·1 is the zero vector with no arithmetic error anywhere in it. Its 1 zero eigenvalue counts the connected components, which breadth-first search also puts at 1; the smallest non-zero eigenvalue is 2 and the largest computed zero is 2.7·10⁻¹⁷, a gap of 7.42·10¹⁶. The quadratic form xᵀLx is Σ over edges of (xᵢ − xⱼ)², which at the alternating vector is 64.
family: "split", n: 32
The arguments are the ones A chain with no stationary vector passes. A value drawn at the generator's defaults instead would be a picture no essay asked for and no assertion has been run against.
The 2 components laid out at its own second and third Laplacian eigenvectors, so the picture is the same object the measurements are about. The Laplacian L = D − A is built by subtraction of integers, so every row sums to exactly zero — measured at 0, not at the rounding level — and L·1 is the zero vector with no arithmetic error anywhere in it. Its 2 zero eigenvalues count the connected components, which breadth-first search also puts at 2; the smallest non-zero eigenvalue is 0.03843 and the largest computed zero is 1.67·10⁻¹⁶, a gap of 2.3·10¹⁴. The quadratic form xᵀLx is Σ over edges of (xᵢ − xⱼ)², which at the alternating vector is 124.
family: "grid", n: 36
The arguments are the ones A distance computed by a solve passes. A value drawn at the generator's defaults instead would be a picture no essay asked for and no assertion has been run against.
The grid 6×6 laid out at its own second and third Laplacian eigenvectors, so the picture is the same object the measurements are about. The Laplacian L = D − A is built by subtraction of integers, so every row sums to exactly zero — measured at 0, not at the rounding level — and L·1 is the zero vector with no arithmetic error anywhere in it. Its 1 zero eigenvalue counts the connected components, which breadth-first search also puts at 1; the smallest non-zero eigenvalue is 0.2679 and the largest computed zero is 2.36·10⁻¹⁶, a gap of 1.13·10¹⁵. The quadratic form xᵀLx is Σ over edges of (xᵢ − xⱼ)², which at the alternating vector is 120.
What it checked while drawing
Every figure above asserted its own claims on the way to being drawn, and a claim that failed
would have failed the build rather than drawn a wrong picture. Those assertions used to leave
no trace at all: a passing one returned true and the only evidence the figure had
checked anything was that nothing crashed. The list below is what they actually said, collected
by running this generator with an observer installed — not a description of
what it is believed to check.
10 distinct claims across 6 sets of arguments, grouped below by shape — because most of them are one sentence with a different number in it, and how many separate times that sentence was put to the test is the informative part.
a family the library builds
a graph large enough to have structure and small enough to draw
a graph with at least two vertices
a planted partition with no isolated vertex
a positive weight
every endpoint inside the vertex set
every row of the Laplacian sums to exactly zero
Jacobi needs a symmetric matrix
no edge given twice
no self-loop
Against the rule
It draws a decomposition and prints its residual. It calls
laplacianEig, componentCount,
and every figure above carries the badge — which residualcheck verifies by looking
for it in the emitted SVG rather than by finding the call that builds one. A badge that is
constructed and then left out of the body is the failure that check exists for.
Across the library: the rule bites on 214
of 382 generators —
194 print a residual and
20 are exempt with a published reason;
168 factorise nothing.
Read from lib/residual-rule.js, which is the same body the gate enforces from,
and the gate's last check fails the build if this page and it disagree about any generator.
Where it is called
Changing this generator changes every figure on this list. That is what makes the list worth publishing rather than keeping in a check script.
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.
The matrix that is a graphA chain with no stationary vector
A page with no outgoing links loses forty per cent of the walker's probability in six hundred steps. A directed cycle never converges at all. And on a graph whose links only run one way, the entire rank of half the vertices is exactly one minus the teleportation parameter.
The matrix that is a graphA count that comes out of a determinant
The number of spanning trees of a graph is the determinant of its grounded Laplacian, so it is a whole number known in advance. The elimination that computes it is backward stable at every size — and from sixteen vertices the answer is wrong, because the count has seventeen digits and a binary64 has sixteen.
The matrix that is a graphA distance computed by a solve
Effective resistance is the one quantity in this field with no combinatorial route to it — it is defined by a linear system. On a small unweighted graph the answer is a ratio of two integers, so for once the error is known rather than estimated, and every resistance in a graph has to add up to a number fixed in advance.
The matrix that is a graphA graph with a tenth of the edges
Keeping 344 of 1,225 edges, sampled by effective resistance and reweighted, preserves every eigenvalue of the Laplacian to within a factor of 1.7. It preserves no degree — half of them are wrong by more than a third — and it takes the diameter from one to three.
The matrix that is a graphA matrix with no numbers in it
A graph arrives as vertices and edges. Two different matrices can be built from it, they answer different questions, and one of them has a null vector that is exact — the only object on this site whose kernel is known before anything runs.
The matrix that is a graphA partition decided in the last digit
On a graph with a symmetry there is no Fiedler vector — there is a plane, and every vector in it is an exact eigenvector. Twenty-four runs with the edge weights nudged by 10⁻¹² return ten different partitions of a cycle and, on a hypercube, two different qualities of answer.
The matrix that is a graphA preconditioner that is a tree
Every eigenvalue of a tree-preconditioned Laplacian is at least one and at most the total stretch — a combinatorial integer with no arithmetic in it. Measured, the bound is two to four times loose, and on a grid the preconditioner makes the conditioning worse by a factor of 1.85 at every size.
The matrix that is a graphA ranking that is an eigenvector
PageRank is the stationary vector of a walk that follows links with probability α and jumps at random otherwise. The iteration and the elimination agree to 4·10⁻¹⁷. What α is set to changes which pages come third, fourth and fifth.
The matrix that is a graphA ranking whose order is not determined
Of the fourteen adjacent comparisons in a top-fifteen, fourteen survive perturbing the arithmetic at the rounding level, eleven survive moving the teleportation parameter across its usual range, and three survive removing one link. The computation is the strongest part of the answer.
The matrix that is a graphAn eigenvector that must not change sign
Perron's theorem says the leading eigenvector of a connected nonnegative matrix is strictly positive. On a clique with a long tail, four of its thirty-six entries come back negative — and beside them is the one two-sided bound on this site that is proved rather than estimated.
The matrix that is a graphEliminating a vertex is a graph operation
Gaussian elimination on a Laplacian deletes a vertex and joins its neighbours into a clique with conductances wᵢwⱼ over Σw. The matrix that remains is still a graph — symmetric, zero row sums, nonpositive off the diagonal — and the ordering decides whether the fill is thirty-one edges or four hundred and sixty-five.
The matrix that is a graphThe rate is the second eigenvalue
A walk forgets where it started at a rate the graph's second eigenvalue names exactly. Across three orders of magnitude in the step count the prediction is five per cent high — and the published rate for PageRank is right for a reason nobody states, which is that a link graph is in pieces.
The matrix that is a graphThe spectrum is not the graph
Two graphs on six vertices with the same Laplacian characteristic polynomial — as integer polynomials, not to fourteen digits. One contains a triangle; the other is bipartite. Every method in this field that reads only the spectrum is answering about the class.
The matrix that is a graphThe 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.
The matrix that is a graphThe vertex nobody solves for
A Laplacian is singular, so every solve with one has to remove its kernel first. There are three ways, they agree to fourteen digits, and the one everybody uses carries a free parameter that no account of the method mentions and that moves the condition number by nine hundred.
The matrix that is a graphTwo Laplacians of one graph
D − A and D^{-1/2}(D − A)D^{-1/2} are built from the same object, are not similar to each other, and answer different questions. On a graph whose degrees are equal they coincide. On one whose degrees span an order of magnitude their second eigenvalues are sixteen times apart.