Session-authored (Fable 5 assisted)

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.

✓ 6 results · all verified · 2 also independently AI-judged

Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs. The 4 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.

Finite Probability and the Probabilistic Method — Examples and Counterexamples

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

None yet.

5 · Examples, counterexamples and false statements

ExampleConstruction: Literature-sourcedVerification: AI-adaptedprecheck passaudited 2026-08-13Open item page →

The expected number of triangles in $G (n, p)$ is $(\binom{n}{3}) p^{3}$

Example

Let $T$ be the number of triangles in $G (n, p)$ . Then $E [T] = (\binom{n}{3}) p^{3},$ and $Var (T) = (\binom{n}{3}) (p^{3} - p^{6}) + 2 (\binom{n}{2}) (\binom{n - 2}{2}) (p^{5} - p^{6}) .$

Facts & Assumptions

Given: The random graph $G (n, p)$ and its triangle count $T$ .

[L1]

$G (n, p)$ has independent Bernoulli edge coordinates (The Erdős-Rényi finite random graph $G (n, p)$ ).

[L2]

A prescribed set of $r$ present edges has probability $p^{r}$ (A prescribed set of present and absent edges in $G (n, p)$ has product probability).

[L3]

Indicators count occurrences and expectation is linear (Indicators turn event probabilities, intersections, and finite counts into expectations and products, Expectation is linear for every finite family of random variables, without any independence hypothesis).

[L4]

There are $(\binom{n}{3})$ vertex triples and $(\binom{n}{2})$ vertex pairs (The set $[A]^{k}$ of $k$ -element subsets and the binomial coefficient $(\binom{n}{k}) : = ∣ [n]^{k} ∣$ ).

[L5]

Variance and covariance obey their centred-product definitions, and the variance of a finite sum is the sum of individual variances plus twice the unordered pairwise covariances (Variance, standard deviation, and covariance on a finite probability space, Variance of a finite sum as the sum of all variances and covariances).

Verification

technique · direct

1.1

Write $T = \sum_{Q} I_{Q}$ , with $Q$ ranging over three-element vertex sets. Each $I_{Q}$ requires three present edges and has expectation $p^{3}$ , so $E [T] = (\binom{n}{3}) p^{3}$ .

L2L3L4

1.2

Each indicator has variance $p^{3} - p^{6}$ . Two distinct triangles are independent unless they share an edge; if they share an edge, their joint occurrence requires five edges and their covariance is $p^{5} - p^{6}$ .

L1L2L5algebra

1.3

An unordered pair of triangles sharing an edge is determined by the common edge and the two distinct extra vertices, so there are $(\binom{n}{2}) (\binom{n - 2}{2})$ such pairs.

2.1

Sum the individual variances and twice the unordered covariances to obtain the formula. For $n < 3$ all relevant binomial coefficients vanish; for $p = 0, 1$ the variance is zero.

step 1.1step 1.2step 1.3L5∎

ExampleConstruction: AI-adaptedVerification: AI-adaptedprecheck passaudited 2026-08-13Open item page →

First- and second-moment bounds for a nonempty Bernoulli random subset

Example

Retain each element of $[n]$ independently with probability $p$ , and let $X$ be the size of the random subset. Then $E [X] = n p, E [X^{2}] = n p (1 - p) + n^{2} p^{2}, P (X > 0) = 1 - (1 - p)^{n} .$ When $n p > 0$ , the first- and second-moment bounds give $P (X > 0) \leq n p, P (X > 0) \geq \frac{n p}{1 - p + n p} .$

Facts & Assumptions

Given: Naturals $n$ and a real $p \in [0, 1]$ .

[L1]

$X$ is a sum of $n$ mutually independent Bernoulli $(p)$ variables, and mutual independence factors their joint attained-value probabilities (Bernoulli random variables and binomial random variables as sums of independent Bernoulli trials, Pairwise and mutual independence of finite-valued random variables).

[L2]

Its mean and variance are $n p$ and $n p (1 - p)$ (A Bernoulli $(p)$ variable has mean $p$ and variance $p (1 - p)$ ; a binomial $(n, p)$ variable has mean $n p$ and variance $n p (1 - p)$ ).

[L3]

$Var (X) = E [X^{2}] - E [X]^{2}$ ( $Var (X) = E [X^{2}] - E [X]^{2}$ and $Cov (X, Y) = E [X Y] - E [X] E [Y]$ ).

[L4]

Markov and the second-moment theorem give their respective upper and lower bounds (Markov's inequality on a finite probability space, The finite second-moment bound $P (X \neq 0) \geq E [X]^{2} / E [X^{2}]$ when $E [X^{2}] > 0$ ).

Verification

technique · cases

1.1

The event $X = 0$ means every retention coordinate is zero, so $P (X > 0) = 1 - (1 - p)^{n}$ .

1.2

The identity [L3] and [L2] give $E [X^{2}] = n p (1 - p) + n^{2} p^{2}$ .

L2L3algebra

1.3

If $n p = 0$ , then $n = 0$ or $p = 0$ , and $X = 0$ almost surely; all three displayed exact formulas give zero where appropriate, while the second-moment ratio is not formed.

assume-case zeroL1L2

2.1

If $n p > 0$ , Markov at threshold $1$ gives $P (X > 0) \leq n p$ , and the second-moment bound with steps 1.1 and 1.2 gives $P (X > 0) \geq (n p)^{2} / (n p (1 - p) + n^{2} p^{2}) = n p / (1 - p + n p)$ .

assume-case positivestep 1.1step 1.2L4algebra

3.1

The cases are exhaustive. At $p = 1$ and $n > 0$ , the exact probability is $1$ and the second-moment lower bound is $n p / (1 - p + n p) = 1$ , while the Markov upper bound is $n p = n$ and is vacuous for $n \geq 2$ .

step 1.3step 2.1cases-exhaustive∎

ExampleConstruction: Literature-sourcedVerification: AI-adaptedprecheck passaudited 2026-08-13Open item page →

The random-colouring proof of $R (k, k) > 2^{k / 2}$

Example

For every natural $k \geq 3$ , a uniformly random red-blue colouring of the edges of a suitable complete graph proves the strict diagonal Ramsey bound $R (k, k) > 2^{k / 2} .$

Facts & Assumptions

Given: A natural $k \geq 3$ and $n = ⌊ 2^{k / 2} ⌋$ .

[L1]

A uniform red-blue edge colouring is equivalently $G (n, 1 / 2)$ (The Erdős-Rényi finite random graph $G (n, p)$ ).

[L2]

Prescribing $r$ edge colours has probability $2^{- r}$ (A prescribed set of present and absent edges in $G (n, p)$ has product probability).

[L3]

Probability of a finite union is at most the sum of its event probabilities, complements have complementary probabilities, and positive probability yields a witness (The finite union bound, Normalization, nonnegativity, monotonicity, complements, and differences in a finite probability space, An event of positive probability in a finite probability space is nonempty).

[L4]

$R (k, k)$ is the least order forcing a monochromatic $k$ -clique, and the published theorem states the same strict bound (The off-diagonal Ramsey number $R (s, t)$ as the least $N$ with $N \to (s, t)^{2}$ , for positive $s, t$ , Erdős's finite counting bound $R (k, k) > 2^{k / 2}$ for every $k \geq 3$ ).

[L5]

Binomial coefficients have the factorial formula, and $n$ is the integer part of $2^{k / 2}$ (The set $[A]^{k}$ of $k$ -element subsets and the binomial coefficient $(\binom{n}{k}) : = ∣ [n]^{k} ∣$ , $(\binom{n}{k}) k! (n - k)! = n!$ for $k \leq n$ ; hence $(\binom{n}{k}) k! = n^{\underline{k}}$ , the quotient $n! / (k! (n - k)!)$ is a natural number, and $(\binom{n}{k}) = (\binom{n}{n - k})$ , The factorial $n!$ and the falling factorial $n^{\underline{k}}$ , defined by recursion in $N$ , Rational powers $a^{r}$ of a positive base, Monotonicity of $r \mapsto a^{r}$ and of $a \mapsto a^{r}$ , Integer part: for every real $x$ there is exactly one integer $m$ with $m \leq x < m + 1$ ).

Verification

technique · constructive

1.1

Construct the random colouring by colouring every edge independently and uniformly red or blue. A fixed $k$ -set is monochromatic with probability $2 \cdot 2^{- (\binom{k}{2})} = 2^{1 - (\binom{k}{2})}$ .

L1L2construct

2.1

The union bound over all $k$ -sets gives failure probability at most $2 (\binom{n}{k}) 2^{- (\binom{k}{2})} \leq 2 n^{k} 2^{- (\binom{k}{2})} / k! \leq 2^{1 + k / 2} / k!$ .

step 1.1L3L5algebra

3.1

At $k = 3$ , $3! = 6 > 2^{5 / 2}$ . If $k! > 2^{1 + k / 2}$ for $k \geq 3$ , then $(k + 1)! = (k + 1) k! > 2^{1 + (k + 1) / 2}$ because $k + 1 > \sqrt{2}$ . Hence the final bound in step 2.1 is less than $1$ for every $k \geq 3$ .

step 2.1algebra

4.1

By [L3] a colouring with no monochromatic $k$ -set exists on $n$ vertices, so $R (k, k) > n$ . Since $R (k, k)$ is an integer and $n = ⌊ 2^{k / 2} ⌋$ , this implies $R (k, k) > 2^{k / 2}$ and agrees with [L4].

step 3.1L3L4L5discharge-construct∎

ExampleConstruction: AI-adaptedVerification: AI-adaptedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-13Open item page →

Checking the symmetric local-lemma condition for a sparse uniform hypergraph

Example

For any natural $q$ , form a $5$ -uniform hypergraph from $q$ disjoint blocks, each block consisting of two edges that meet in one vertex and are otherwise disjoint. Every edge meets exactly one other edge. The Local Lemma proves the hypergraph two-colourable for every $q$ , while the first-moment edge-count criterion applies only when $2 q < 16$ .

Facts & Assumptions

Given: The hypergraph construction in the Example.

[L1]

Fewer than $2^{k - 1}$ edges is sufficient for first-moment two-colourability (Every $k$ -uniform hypergraph with fewer than $2^{k - 1}$ edges is $2$ -colourable).

[L2]

The Local-Lemma criterion is $e (d + 1) \leq 2^{k - 1}$ when every edge meets at most $d$ other edges (A $k$ -uniform hypergraph is $2$ -colourable when every edge meets at most $d$ other edges and $e (d + 1) \leq 2^{k - 1}$ ).

[L3]

$e = \sum_{j \geq 0} 1 / j!$ , and at $x = 1, N = 2$ the exponential tail from $j = 3$ onward is at most $1 / 3$ (The real exponential function and the number $e$ by a power series, A geometric bound for tails of the exponential series).

Verification

technique · direct

1.1

Every edge has five vertices and meets only its block partner, so $k = 5$ and $d = 1$ .

given

2.1

By [L3], $e \leq 1 + 1 + 1 / 2 + 1 / 3 = 17 / 6 < 3$ , so $2 e < 6 < 16$ . Hence [L2] gives a proper two-colouring for every $q$ , including $q = 0$ .

step 1.1L2L3algebra

3.1

The hypergraph has $2 q$ edges, so [L1] applies only when $2 q < 2^{4} = 16$ . For $q \geq 8$ , the Local Lemma still applies while this first-moment criterion does not.

step 1.1L1algebra∎

ExampleConstruction: AI-adaptedVerification: AI-adaptedprecheck passaudited 2026-08-13Open item page →

A parameter ledger for the high-girth, high-chromatic alteration proof

Example

For the targets $k = 2$ and $ℓ = 3$ , choose $n = 2^{60}, p = n^{- 5 / 6} = 2^{- 50}, s = n / 4 = 2^{58} .$ These parameters make both failure probabilities in the alteration proof less than $1 / 2$ .

Facts & Assumptions

Given: The explicit parameters in the Example.

[L1]

The expected number of cycles of length at most $3$ is at most $n^{3} p^{3} / 6$ (The expected number of cycles of length at most $ℓ$ in $G (n, p)$ ).

[L2]

$P (α (G (n, p)) \geq s) \leq \exp (s \log n - p (\binom{s}{2}))$ ( $P (α (G (n, p)) \geq s) \leq (\binom{n}{s}) (1 - p)^{(\binom{s}{2})} \leq n^{s} \exp (- p (\binom{s}{2}))$ for $s \leq n$ ).

[L3]

The exponential is strictly increasing and positive, $\exp (- x) = 1 / \exp (x)$ , $1 + x \leq \exp (x)$ , and the logarithm is the increasing inverse of the exponential with its product law (The real exponential function and the number $e$ by a power series, The natural logarithm as the inverse of the exponential function, Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm, $1 + x \leq \exp (x)$ for every real $x$ , hence $(1 - p)^{m} \leq \exp (- m p)$ , The exponential is positive and satisfies $\exp (- x) = 1 / \exp (x)$ , The exponential function is strictly increasing).

[L4]

Markov bounds nonnegative upper tails; the union bound controls finite unions; complements have complementary probabilities; and positive probability gives a witness (Markov's inequality on a finite probability space, The finite union bound, Normalization, nonnegativity, monotonicity, complements, and differences in a finite probability space, An event of positive probability in a finite probability space is nonempty).

[L5]

The high-girth alteration deletes one vertex per short cycle and compares the surviving order with the independence number (For all positive $k, ℓ$ , some finite graph has girth greater than $ℓ$ and chromatic number greater than $k$ ).

Verification

technique · constructive

1.1

Here $n^{3} p^{3} / 6 = n^{1 / 2} / 6$ , so [L4] at the threshold $n / 2$ bounds the short-cycle failure probability by $n^{- 1 / 2} / 3 < 1 / 2$ .

L1L4algebra

1.2

Since $p (s - 1) / 2 = 2^{- 51} (2^{58} - 1) > 127$ , while [L3] gives $\log n = 60 \log 2 \leq 60$ , one has $s \log n - p (\binom{s}{2}) = s (\log n - p (s - 1) / 2) < - 67 s < - 1$ . Thus [L2] and [L3] bound the independence failure probability by a number less than $\exp (- 1) = 1 / e \leq 1 / 2$ .

L2L3algebra

2.1

By [L4], the union of the two failure events has probability less than $1$ , so its complement has positive probability and contains a graph with fewer than $n / 2$ triangles and independence number below $n / 4$ . Delete one vertex per triangle. More than $n / 2$ vertices survive, no triangle survives, and any two-colouring would have an independent colour class larger than $n / 4$ .

step 1.1step 1.2L4L5construct

3.1

Hence the survivor has girth greater than $3$ and chromatic number greater than $2$ , with every integrality and strict inequality explicit.

step 2.1L5discharge-construct∎

CounterexampleConstruction: AI-adaptedVerification: AI-adaptedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-13Open item page →

Expectation equal to $1$ does not force a nonnegative integer-valued variable to vanish somewhere

Statement refuted

If a nonnegative integer-valued random variable satisfies $E [X] \leq 1$ , then some outcome has $X = 0$ .

Facts & Assumptions

Given: The uniform probability space on a singleton and its constant random variable $X = 1$ .

[L1]

A nonempty singleton carries a uniform finite probability space (The uniform probability space on a nonempty finite set).

[L2]

Expectation is the finite weighted sum of values (Expectation of a real random variable on a finite probability space).

[L3]

The first-moment avoidance conclusion assumes the strict inequality $E [X] < 1$ (The first-moment method for avoiding or forcing a finite count of bad events).

Counterexample

technique · constructive

1.1

Construct $X$ to equal $1$ on the unique outcome. That outcome has weight $1$ , so $E [X] = 1$ .

givenL1L2construct

1.2

The event ${X = 0}$ is empty.

given

2.1

Thus the weak threshold $E [X] \leq 1$ does not force a zero outcome; the strict hypothesis in [L3] is necessary.

step 1.1step 1.2L3discharge-construct∎

Sources

Standard references

Recommended treatments; not extraction sources.

Finite Probability and the Probabilistic Method — Examples and Counterexamples

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

5 · Examples, counterexamples and false statements

The expected number of triangles in G(n,p)G(n,p) is (n3)p3(3n​)p3

Example

Facts & Assumptions

Verification

First- and second-moment bounds for a nonempty Bernoulli random subset

Example

Facts & Assumptions

Verification

The random-colouring proof of R(k,k)>2k/2R(k,k)>2k/2

Example

Facts & Assumptions

Verification

Checking the symmetric local-lemma condition for a sparse uniform hypergraph

Example

Facts & Assumptions

Verification

A parameter ledger for the high-girth, high-chromatic alteration proof

Example

Facts & Assumptions

Verification

Expectation equal to 11 does not force a nonnegative integer-valued variable to vanish somewhere

Statement refuted

Facts & Assumptions

Counterexample

Sources

Standard references

The expected number of triangles in $G (n, p)$ is $(\binom{n}{3}) p^{3}$

The random-colouring proof of $R (k, k) > 2^{k / 2}$

Expectation equal to $1$ does not force a nonnegative integer-valued variable to vanish somewhere