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.

An isolate is excluded from Ncut and reinserted separately

Example

Let $V = {1, 2, 3}$ with $w_{12} = w_{21} = 1$ and every other weight zero. For the algorithm inputs, take $n = 3$ , $p = 1$ , $x_{i} = i \in R$ for $1 \leq i \leq 3$ , and the constant deterministic graph builder $G : (R^{1})^{3} \to R^{3 \times 3}$ defined by $G (y_{1}, y_{2}, y_{3}) = W = (w_{i j})$ for every input tuple. In mode $normalized$ with $k = 1$ and row normalization disabled (the default), the positive-degree vertex set is $V_{+} = {1, 2}$ , the active Ncut cluster is ${1, 2}$ with value $0$ , and vertex $3$ is returned separately as the singleton ${3}$ without entering any Ncut denominator.

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

Vertices $1$ and $2$ are joined by their unit-weight edge; vertex $3$ is isolated. The relative coordinates are only for display.

diagram failed to render:
\begin{tikzpicture}
\node[draw,circle] (v1) at (0,0) {$1$};
\node[draw,circle] (v2) at (1.5,0) {$2$};
\node[draw,circle] (v3) at (4,0) {$3$};
\draw (v1)--node[above] {$1$}(v2);
\end{tikzpicture}

Facts & Assumptions

Given: $V = {1, 2, 3}$ , with $w_{12} = w_{21} = 1$ and every other weight zero, the data, dimensions, and constant graph builder $G$ from the Example (so the computed matrix is exactly $W$ ), normalized mode, $k = 1$ , and row normalization disabled.

[F1]

Finite weighted graph Laplacian: $d_{i} = \sum_{j} w_{i j}$ , $V_{+} = {i : d_{i} > 0}$ , and $L_{s y m, +} = D_{+}^{- 1 / 2} L_{+} D_{+}^{- 1 / 2}$ .

[F2]

RatioCut and normalized cut for a finite weighted graph: Ncut sums $cut (A_{r}, A_{r}^{c}) / vol (A_{r})$ over a partition of $V_{+}$ into nonempty parts.

[F3]

Quadratic form and kernel of a weighted graph Laplacian: the kernel consists of vectors constant on each support component.

[F4]

Deterministic weighted spectral clustering with explicit isolate and eigenspace conventions: normalized mode uses only positive-degree vertices, chooses the prescribed zero-mode eigenvector first, runs the specified Lloyd updates, and appends isolates as separate singleton outputs.

Verification

1.1givenF1algebra

The degrees are $(1, 1, 0)$ , so $V_{+} = {1, 2}$ , $D_{+} = I_{2}$ , and $L_{+} = L_{s y m, +} = (\begin{array}{cc} 1 & - 1 \\ - 1 & 1 \end{array})$ .

2.1givenF3F4step 1.1algebra

The active support graph is connected, so [F3] gives a one-dimensional zero eigenspace spanned by $(1, 1)$ . Its prescribed unit vector is $q_{0} = (1, 1) / \sqrt{2}$ , and it is the single eigenvector used when $k = 1$ .

3.1givenF4step 2.1algebra

Both embedding rows are $1 / \sqrt{2}$ . The first and only Lloyd center is the first row; both points receive its label, its mean remains $1 / \sqrt{2}$ , and the labels and center are unchanged. Thus the active cluster returned is ${1, 2}$ , after which [F4] appends ${3}$ separately.

4.1F1F2step 1.1step 3.1algebra∎

The active part has cut $0$ and volume $d_{1} + d_{2} = 2$ , so its Ncut value is $0$ . Vertex $3$ has volume $0$ but is not in $V_{+}$ , so it appears in no Ncut denominator.

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)