ExampleConstruction: AI-generatedVerification: AI-adaptedPipeline-generatedprecheck passaudited 2026-10-02

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.

Conditional expectation derandomizes Max-Cut on a triangle

Example

Run the conditional-expectation algorithm on $K_{3}$ with vertices $v_{1}, v_{2}, v_{3}$ in that order. The initial expected cut size is $3 / 2$ . Fix $v_{1} = 0$ . Setting $v_{2} = 0$ leaves conditional expectation $1$ , while setting $v_{2} = 1$ gives $2$ , so choose $v_{2} = 1$ . The two choices for $v_{3}$ then both give final cut size $2$ . Thus the returned cut has $2 \geq 3 / 2$ edges.

Facts & Assumptions

Given: The complete graph $K_{3}$ on $V = {v_{1}, v_{2}, v_{3}}$ with edge set $E = {v_{1} v_{2}, v_{2} v_{3}, v_{1} v_{3}}$ , so $m = 3$ , and the independent fair bits $b_{1}, b_{2}, b_{3}$ of the conditional-expectation algorithm applied in the vertex order $v_{1}, v_{2}, v_{3}$ .

[F1]

For a graph with $m$ edges the independent uniform placement crosses $m / 2$ edges in expectation, and every placement crosses at most $m$ edges, so ${OPT}_{M a x C u t} \leq m$ . (A random cut crosses half the edges in expectation)

[F2]

The conditional-expectation algorithm fixes the vertices one at a time, choosing at each step the value of the next bit whose conditional expected final cut size is larger, with ties resolved by the value $0$ ; its conditional expectation is the average of the cut size over the equally weighted completions, and it is computable from the finished and unfinished edge contributions. (Conditional expectation yields a deterministic half-approximation for Max-Cut)

[F3]

For Max-Cut the objective is the number of crossing edges and ${OPT}_{M a x C u t}$ is the attained maximum over the finitely many placements. (Optimization problems and approximation ratios)

Verification

technique · direct

1.1F1F2givenconstruct

For $K_{3}$ the edge set has $m = 3$ elements, so by [F1] the initial conditional expectation over no fixed bits is the expected cut size $m / 2 = 3 / 2$ ; the algorithm of [F2] now fixes $b_{1}, b_{2}, b_{3}$ in order.

2.1F2step 1.1algebra

At the first step every one of the three edges has at least one unfixed endpoint, so each contributes $1 / 2$ to both candidates for $b_{1}$ and both conditional expectations equal $3 / 2$ ; the tie rule of [F2] selects $b_{1} = 0$ . With $b_{1} = 0$ fixed, the candidate $b_{2} = 0$ finishes the edge $v_{1} v_{2}$ as non-crossing and leaves $v_{2} v_{3}$ and $v_{1} v_{3}$ with an unfixed endpoint each, giving conditional expectation $0 + \frac{1}{2} + \frac{1}{2} = 1$ , while the candidate $b_{2} = 1$ makes $v_{1} v_{2}$ crossing and again leaves the other two edges half-crossing, giving $1 + \frac{1}{2} + \frac{1}{2} = 2$ ; since $2 > 1$ the algorithm fixes $b_{2} = 1$ .

3.1F2step 2.1algebra

With $b_{1} = 0$ and $b_{2} = 1$ fixed, the candidate $b_{3} = 0$ gives crossing edges $v_{1} v_{2}$ and $v_{2} v_{3}$ but not $v_{1} v_{3}$ , a cut size of $2$ , and the candidate $b_{3} = 1$ gives crossing edges $v_{1} v_{2}$ and $v_{1} v_{3}$ but not $v_{2} v_{3}$ , also a cut size of $2$ ; both conditional expectations equal the actual final cut size because every edge is then finished, and the tie rule fixes $b_{3} = 0$ .

4.1F1F3step 1.1step 3.1algebra∎

The returned placement $(b_{1}, b_{2}, b_{3}) = (0, 1, 0)$ has cut ${v_{1}, v_{3}}$ against ${v_{2}}$ with crossing edges $v_{1} v_{2}$ and $v_{2} v_{3}$ , so its cut size is $2 \geq 3 / 2 = m / 2$ , and this equals ${OPT}_{M a x C u t} (K_{3}) = 2$ , since a triangle placement crosses at most two of its three edges and the displayed cut crosses exactly two. The instance therefore realizes the conditional-expectation guarantee with the initial expectation $3 / 2$ .

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

7 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

Cornell CS 4820, Lecture notes on randomized approximation algorithms, §1.1.2 conditional-expectation procedure, PDF pp. 2–3 (standard reference, not scraped)