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.

✓ 4 results · all verified · 3 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 1 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.

Polynomial Rödl, Virality and Erdős–Hajnal Equivalence — Examples

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

None yet.

5 · Examples, counterexamples and false statements

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-08-26Open item page →

The singleton family ${P_{3}}$ is viral

Example

The singleton family ${P_{3}}$ is viral.

Facts & Assumptions

Given: The three-vertex path $P_{3}$ .

[L1]

Every graph on at most three vertices has the Erdős–Hajnal property (Every graph on at most three vertices has the Erdős–Hajnal property).

[L2]

For a single graph, the Erdős–Hajnal property, the polynomial Rödl property, and virality are equivalent (For a single graph, the Erdős–Hajnal property, the polynomial Rödl property, and virality are equivalent).

[L3]

$P_{3}$ is the standard three-vertex path (Empty and complete graphs, complete bipartite graphs, and the convention that $P_{n}$ and $C_{n}$ have $n$ vertices).

Verification

technique · direct

1.1

By [L3], the graph $P_{3}$ has three vertices, so [L1] gives the Erdős–Hajnal property for $P_{3}$ .

L1L3

2.1

Applying [L2] to the graph $P_{3}$ of step 1.1 shows that the singleton family ${P_{3}}$ is viral.

step 1.1L2∎

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passaudited 2026-08-26Open item page →

A family containing $K_{1}$ is viral for vacuous reasons

Example

Every finite family of graphs containing $K_{1}$ is viral, but only vacuously: for $ϵ \in (0, \frac{1}{2})$ no nonempty graph satisfies the required $K_{1}$ -copy bound.

Facts & Assumptions

Given: A finite family $F$ with $K_{1} \in F$ , a real $ϵ \in (0, \frac{1}{2})$ , and a nonempty finite graph $G$ .

[L1]

Virality asks for the implication in The viral property for a finite forbidden family.

[L2]

${ind}_{K_{1}} (G)$ counts the induced embeddings of the one-vertex graph in $G$ (The induced-embedding count ${ind}_{H} (G)$ , Empty and complete graphs, complete bipartite graphs, and the convention that $P_{n}$ and $C_{n}$ have $n$ vertices).

[L3]

For a positive base, $ϵ^{d} = \exp (d \log ϵ)$ ; the logarithm and exponential are strictly increasing, and the exponential is positive (Real powers for positive bases, with the zero-base positive-exponent convention, Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm, The exponential function is strictly increasing, The exponential is positive and satisfies $\exp (- x) = 1 / \exp (x)$ ).

Verification

technique · direct

1.1

Each vertex of $G$ determines one induced embedding of $K_{1}$ into $G$ , so [L2] gives ${ind}_{K_{1}} (G) = ∣ V (G) ∣$ .

2.1

If $d \geq 1$ , then $0 < ϵ < 1$ gives $\log ϵ < 0$ and therefore $d \log ϵ \leq \log ϵ < 0$ . By [L3], $0 < ϵ^{d} \leq ϵ < 1$ , so $ϵ^{d} ∣ V (G) ∣ < ∣ V (G) ∣ = {ind}_{K_{1}} (G)$ . Thus the defining viral inequality for $K_{1}$ can hold for no nonempty graph.

step 1.1L3algebra

3.1

Since the antecedent in [L1] has no nonempty instance, every exponent $d \geq 1$ witnesses the viral implication vacuously. Therefore any finite family containing $K_{1}$ is viral.

step 2.1L1∎

CounterexampleConstruction: AI-generatedVerification: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-08-26Open item page →

The polynomial Rödl witness need not be the whole graph

Statement refuted

Whenever a finite family has the polynomial Rödl property, the restricted set guaranteed by that property can always be chosen to be the whole graph.

Facts & Assumptions

Given: A real $ϵ \in (0, \frac{1}{2})$ and the graph $G : = K_{N} ⊔ K_{N}$ with $N > 1 / (1 - 2 ϵ)$ .

[L1]

Every graph on at most three vertices has the Erdős–Hajnal property (Every graph on at most three vertices has the Erdős–Hajnal property).

[L2]

[L3]

$P_{3}$ is the three-vertex path, and $K_{N}$ is the complete graph on $N$ vertices (Empty and complete graphs, complete bipartite graphs, and the convention that $P_{n}$ and $C_{n}$ have $n$ vertices).

[L4]

A set is $ϵ$ -restricted when it is $ϵ$ -sparse or $ϵ$ -dense ( $c$ -sparse, $c$ -dense and $c$ -restricted vertex sets).

[L5]

A graph is $P_{3}$ -free when it has no induced copy of the three-vertex path ( $H$ -free and $F$ -free graphs under the induced-subgraph convention, Empty and complete graphs, complete bipartite graphs, and the convention that $P_{n}$ and $C_{n}$ have $n$ vertices).

Counterexample

technique · constructive

1.1

The graph $G$ is $P_{3}$ -free: three vertices in one clique induce a triangle, three vertices meeting both cliques induce either one edge or no edge, and none of those induced subgraphs is $P_{3}$ .

L3L5construct

1.2

Let $X : = V (G)$ . Every vertex of $X$ has exactly $N - 1$ neighbours and exactly $N$ non-neighbours inside $X$ . Since $N > 1 / (1 - 2 ϵ)$ , one has $N - 1 > 2 ϵ N = ϵ ∣ X ∣$ , so $X$ is not $ϵ$ -sparse; and because $ϵ < 1 / 2$ , one also has $N > ϵ ∣ X ∣$ , so $X$ is not $ϵ$ -dense. Thus $X$ is not $ϵ$ -restricted by [L4].

L4algebra

1.3

One clique component of $G$ is $0$ -dense and therefore $ϵ$ -restricted, so the polynomial Rödl conclusion for $G$ is realized by a proper subset of vertices rather than by the whole graph.

L4algebra

1.4

By [L3], the graph $P_{3}$ has three vertices, so [L1] gives the Erdős–Hajnal property for $P_{3}$ . Applying [L2] then shows that the singleton family ${P_{3}}$ has the polynomial Rödl property.

L1L2L3

2.1

Steps 1.2 and 1.3 show that the theorem's restricted witness need not be $V (G)$ itself, refuting the claim.

step 1.2step 1.3discharge-construct∎

CounterexampleConstruction: AI-generatedVerification: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-08-26Open item page →

The empty forbidden family is not Erdős–Hajnal

Statement refuted

The empty forbidden family has the Erdős–Hajnal property.

Facts & Assumptions

Given: The empty family $\emptyset$ of graphs.

[L1]

A graph is $\emptyset$ -free exactly when it is $H$ -free for every $H \in \emptyset$ , which is vacuous ( $H$ -free and $F$ -free graphs under the induced-subgraph convention).

[L2]

The hereditary class of all finite graphs does not have the Erdős–Hajnal property (The hereditary class of all finite graphs does not have the Erdős–Hajnal property).

[L3]

On a finite family, the Erdős–Hajnal property, the polynomial Rödl property, and virality are equivalent (For a finite family, the Erdős–Hajnal property, the polynomial Rödl property, and virality are equivalent).

Counterexample

technique · direct

1.1

By [L1], every finite graph is $\emptyset$ -free. So the class of $\emptyset$ -free graphs is exactly the class of all finite graphs.

2.1

Applying [L2] to the class identified in step 1.1 shows that the empty family does not have the Erdős–Hajnal property.

step 1.1L2

3.1

Therefore the claim is false. By [L3], the empty family also has neither of the other two equivalent properties from the A page.

step 2.1L3∎

Polynomial Rödl, Virality and Erdős–Hajnal Equivalence — Examples

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

5 · Examples, counterexamples and false statements

The singleton family {P3}{P3​} is viral

Example

Facts & Assumptions

Verification

A family containing K1K1​ is viral for vacuous reasons

Example

Facts & Assumptions

Verification

The polynomial Rödl witness need not be the whole graph

Statement refuted

Facts & Assumptions

Counterexample

The empty forbidden family is not Erdős–Hajnal

Statement refuted

Facts & Assumptions

Counterexample

The singleton family ${P_{3}}$ is viral

A family containing $K_{1}$ is viral for vacuous reasons