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.
A polynomial homogeneous set in the auxiliary pattern yields a -restricted union
Statement
Let , let , and let . Let be a blockade in a finite graph such that:
- ;
- all blocks have the same size;
- for every distinct , either is complete to , or both is -sparse to and is -sparse to .
Let satisfy , and let be the graph on defined by
If has a clique or stable set with , then the induced subgraph on
is -restricted and has at least the common block size of the selected blocks.
Facts & Assumptions
Given: The graph , the blockade , the subset , the auxiliary graph , and the homogeneous set from the Statement.
A set is -restricted exactly when it is -sparse or -dense (-sparse, -dense and -restricted vertex sets).
If is -sparse to , then each vertex of has at most neighbours in (Sparsity of one vertex set to another, and weak sparsity of a pair).
If is complete to , then every vertex of is adjacent to every vertex of (Edges between disjoint vertex sets; complete, anticomplete, pure and mixed pairs).
Proof
Proof technique: estimate the internal and external neighbour counts in the union of the selected equal-size blocks.
Let be the common block size. Since , , and , we have .
Now suppose that is a stable set in . For any , the neighbours of inside its own block contribute fewer than vertices. If , then , so the pairs are mutually -sparse and [L2] gives at most neighbours of in . Summing over all other selected blocks, has at most neighbours in .
First suppose that is a clique in . Then [L3] makes every two distinct selected blocks complete. For any , the only possible nonneighbours of inside lie in , so has fewer than nonneighbours in . Step 1.1 gives , so is -dense and hence -restricted by [L1].
Since and , step 1.1 yields . Hence every vertex of has at most neighbours inside , so is -sparse and therefore -restricted by [L1].
Steps 2.1 and 2.2 show that whether is a clique or a stable set, the union is -restricted. Also , so has at least the common block size.
Depends on
Used by
Dependency tree · two levels
9 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, Erdős-Hajnal beyond the five-vertex path, end of the proof of Lemma 2.1 (standard reference, not scraped)