ExampleConstruction: AI-generatedVerification: AI-generatedPipeline-generatedprecheck passjudge pass (gpt-6-luna)

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Disconnected weighted components are zero-cut clusters

Example

Let $V = {1, 2, 3, 4}$ and set $w_{12} = w_{21} = 2$ , $w_{34} = w_{43} = 3$ , with every other entry zero. For the algorithm inputs, take $n = 4$ , $p = 1$ , $x_{i} = i \in R$ for $1 \leq i \leq 4$ , and the constant deterministic graph builder $G : (R^{1})^{4} \to R^{4 \times 4}$ defined by $G (y_{1}, y_{2}, y_{3}, y_{4}) = W = (w_{i j})$ for every input tuple. Use mode $ratio$ and $k = 2$ . The partition ${1, 2}, {3, 4}$ has RatioCut and Ncut equal to $0$ , and deterministic unnormalized spectral clustering with $k = 2$ returns these two components under the specified eigenspace and farthest-first tie rules.

Example references

Ulrike von Luxburg, A Tutorial on Spectral Clustering, Statistics and Computing 17(4), 2007

Jean Gallier, Notes on Elementary Spectral Graph Theory: Applications to Graph Clustering Using Normalized Cuts, 2013

Graph diagram

The four circles are vertices; the left edge has weight $2$ and the right edge has weight $3$ . There are no other edges. The drawing separates components for readability; the verification uses the explicit matrix.

Facts & Assumptions

Given: $V = {1, 2, 3, 4}$ with the only positive weights $w_{12} = w_{21} = 2$ and $w_{34} = w_{43} = 3$ ; the data, dimensions, constant graph builder $G$ , mode $ratio$ , and $k = 2$ are as specified in the Example, so the algorithm computes exactly this $W$ ; RatioCut and Ncut use the definitions in the cited supplier.

[F1]

Finite weighted graph Laplacian: $d_{i} = \sum_{j} w_{i j}$ , $L = D - W$ , and support components are determined by edges with positive weight.

[F2]

RatioCut and normalized cut for a finite weighted graph: RatioCut divides each part cut by cardinality; Ncut divides by volume.

[F3]

Quadratic form and kernel of a weighted graph Laplacian: $\ker L$ consists of vectors constant on each support component.

[F4]

Deterministic weighted spectral clustering with explicit isolate and eigenspace conventions: the algorithm selects the first $k$ eigenvectors ordered by the eigenvalues of $L$ , then applies the stated deterministic farthest-first and Lloyd rules.

Verification

1.1givenF1F3algebra

The degrees are $(2, 2, 3, 3)$ and $L = (\begin{array}{cccc} 2 & - 2 & 0 & 0 \\ - 2 & 2 & 0 & 0 \\ 0 & 0 & 3 & - 3 \\ 0 & 0 & - 3 & 3 \end{array}) .$ Each $2 \times 2$ block with edge weight $a$ has eigenvectors $(1, 1)$ and $(1, - 1)$ with eigenvalues $0$ and $2 a$ . Thus the eigenvalues of $L$ are $0, 0, 4, 6$ , and [F3] identifies the zero eigenspace as the componentwise-constant vectors.

2.1givenF2step 1.1algebra

For $A_{1} = {1, 2}$ and $A_{2} = {3, 4}$ there is no crossing edge, so both cuts are $0$ ; the part sizes are $2, 2$ and volumes are $4, 6$ . Therefore both RatioCut and Ncut equal $0$ . Since their summands are nonnegative, this partition attains the combinatorial minimum for both objectives.

2.2givenF3F4step 1.1constructalgebra

The prescribed first zero-mode vector is $q_{0} = \frac{1}{2} (1, 1, 1, 1)$ . The projection of $e_{1}$ onto the zero eigenspace is $(1 / 2, 1 / 2, 0, 0)$ ; subtracting its projection onto $q_{0}$ gives $(1 / 4, 1 / 4, - 1 / 4, - 1 / 4)$ , whose norm is $1 / 2$ . Thus the second basis vector is $q_{1} = \frac{1}{2} (1, 1, - 1, - 1)$ . The first two eigenvectors therefore give the two row values $(1 / 2, 1 / 2)$ on vertices $1, 2$ and $(1 / 2, - 1 / 2)$ on vertices $3, 4$ .

3.1F4step 2.1step 2.2algebra∎

The first farthest-first center is the row for vertex $1$ ; a farthest row is in the second component, and the smallest-index tie rule selects vertex $3$ . Each component's row has distance $0$ to its corresponding center and distance $1$ to the other. The initial assignments are therefore exactly ${1, 2}$ and ${3, 4}$ ; their means equal the two centers, so the first Lloyd update leaves both labels and centers unchanged and the algorithm returns this partition. Together with steps 2.1 and 2.2, this verifies the stated exact example output.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

8 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Ulrike von Luxburg, A Tutorial on Spectral Clustering, Statistics and Computing 17(4), 2007 (standard reference, not scraped)
Jean Gallier, Notes on Elementary Spectral Graph Theory: Applications to Graph Clustering Using Normalized Cuts, 2013 (standard reference, not scraped)