ExampleConstruction: Literature-sourcedVerification: AI-generatedSession-authored (Fable 5 assisted)precheck passaudited 2026-08-16

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.

The triangle counting lemma is exact for three complete cross-pairs

Statement

Let $X, Y, Z$ be disjoint nonempty vertex sets with every cross-edge between distinct sets present. Every cross-pair is $0$ -regular of density $1$ , and exactly $∣ X ∣ ∣ Y ∣ ∣ Z ∣$ ordered transversal triples span a triangle.

Facts & Assumptions

Given: Three sets with all cross-edges present.

[L1]

The triangle counting lemma bounds the number of transversal triangles from the three pair densities and their regularity (Triangle counting lemma for three pairwise regular vertex sets).

[L2]

Density is the number of ordered cross-edge incidences divided by the product of the set sizes (Edge counts and densities between nonempty vertex sets).

[L3]

A pair is $0$ -regular when every nonempty subpair has the same density as the whole pair ( $ϵ$ -regular pairs and self-regular vertex sets).

Verification

technique · direct

1.1

By [L2], each cross-pair has density $1$ . Every nonempty subpair is also complete and has density $1$ , so each pair is $0$ -regular by [L3].

givenL2L3

1.2

Every $(x, y, z) \in X \times Y \times Z$ has all three required edges and therefore spans a triangle. Conversely, each ordered transversal triangle is one such product choice, giving exactly $∣ X ∣ ∣ Y ∣ ∣ Z ∣$ .

givenalgebra

2.1

Substitution $a = b = c = 1$ and $ϵ = 0$ into [L1] yields the same lower bound $∣ X ∣ ∣ Y ∣ ∣ Z ∣$ , so the bound is exact here.

step 1.1step 1.2L1algebra∎

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · next 3 levels

Direct dependencies and their dependencies through the next three levels: 8 results over 8 levels. An arrow runs from a result to what uses it, and this result sits at the bottom with a heavier outline. Click the chart to enlarge it.

Sources

Y. Zhao, Graph Theory and Additive Combinatorics, Theorem 2.2.1 (standard reference, not scraped)