ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-09-04

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.

Thinning a four-block weakly sparse blockade to directional sparse subblocks

Example

Let $G$ have four pairwise disjoint blocks $A_{1} = {a_{1}, \dots, a_{8}}, A_{2} = {b_{1}, \dots, b_{8}}, A_{3} = {c_{1}, \dots, c_{8}}, A_{4} = {d_{1}, \dots, d_{8}} .$

and suppose the only cross-edges between noncomplete pairs are

$a_{1} b_{1}, a_{2} c_{1}, a_{3} d_{1}, b_{2} c_{2}, b_{3} d_{2}, c_{3} d_{3} .$

Then $(A_{1}, A_{2}, A_{3}, A_{4})$ is a blockade of width $8$ , every noncomplete pair is weakly $1 / 16$ -sparse, and the subblocks

$D_{1} = {a_{7}, a_{8}}, D_{2} = {b_{7}, b_{8}}, D_{3} = {c_{7}, c_{8}}, D_{4} = {d_{7}, d_{8}}$

are pairwise complete or pairwise anticomplete. In particular every formerly weakly sparse pair becomes directionally $0$ -sparse after thinning.

Facts & Assumptions

Given: The graph $G$ and the four blocks $A_{1}, A_{2}, A_{3}, A_{4}$ described in the example.

[L1]

A blockade is an ordered sequence of pairwise disjoint nonempty vertex sets, and its width is the minimum block size (Blockades, their length, their width, and their support).

[L2]

A weakly $c$ -sparse pair $(X, Y)$ satisfies $e_{G} (X, Y) \leq c ∣ X ∣ ∣ Y ∣$ , while directional sparsity bounds the neighbours of each single vertex into the opposite set (Sparsity of one vertex set to another, and weak sparsity of a pair).

Verification

technique · direct adjacency count

1.1

The four blocks are pairwise disjoint and nonempty, each has size $8$ , so $(A_{1}, A_{2}, A_{3}, A_{4})$ is a blockade of width $8$ by [L1]. Every noncomplete pair listed in the example has exactly one cross-edge, hence at most $1 = (1 / 16) \cdot 8 \cdot 8$ cross-edges. Therefore each such pair is weakly $1 / 16$ -sparse by [L2].

L1L2givenalgebra

1.2

None of the vertices $a_{7}, a_{8}, b_{7}, b_{8}, c_{7}, c_{8}, d_{7}, d_{8}$ appears in any of the six displayed cross-edges. Hence every noncomplete pair among $D_{1}, D_{2}, D_{3}, D_{4}$ has no cross-edge at all, so each vertex in one chosen subblock has $0$ neighbours in the other. By [L2], those pairs are directionally $0$ -sparse.

givenL2

2.1

Therefore the thinning $(A_{1}, A_{2}, A_{3}, A_{4}) ⇝ (D_{1}, D_{2}, D_{3}, D_{4})$ exhibits exactly the weak-to-directional sparsity conversion claimed in the example.

step 1.1step 1.2∎

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

10 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

Shenwei Huang, Yiao Ju, and Yidong Zhou, Erdos-Hajnal beyond the five-vertex path, Lemma 2.6 (standard reference, not scraped)