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.
Large almost-pure pair hypotheses yield a complete or anticomplete blockade
Statement
Let , , put , and assume Assume that . Suppose that every induced subgraph of with contains disjoint sets such that
and is complete or anticomplete to . Then contains a complete or anticomplete -blockade.
Facts & Assumptions
Given: The parameters , the graph , and the large almost-pure pair hypothesis on every induced subgraph of size at least .
A pair is pure exactly when it is complete or anticomplete (Edges between disjoint vertex sets; complete, anticomplete, pure and mixed pairs).
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).
Proof
Let be maximal such that has a blockade with for all , with , and with the property that for each , either every later block is complete to , or every later block is anticomplete to . This is possible because , so already satisfies the required lower bounds.
Suppose . The bound implies , and the elementary inequality for gives . Hence , so the hypothesis applies to . Choose disjoint with where the last inequality uses , and with , and complete or anticomplete to . Moreover, where the last inequality follows from and . Because , every earlier block has the same pure relation to both and that it had to . Thus is a longer blockade of the same type, contradicting the maximality of . So .
Let be the set of indices such that every later block is complete to , and let be the set of indices such that every later block is anticomplete to . By construction every index lies in , so one of or has size at least .
If , choose indices from in their inherited order. The corresponding blocks form a complete blockade, and every block has size at least by step 1.1. If instead , the same construction with gives an anticomplete blockade. In either case we obtain a complete or anticomplete -blockade.
Therefore the stated blockade exists.
Depends on
Used by
Dependency tree · two levels
4 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, note after Lemma 2.8 (standard reference, not scraped)