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.
The no-E-copy boundary case of the comb partition
Example
Let and . The one-tooth -comb has special vertex . In the structural partition take , and the singleton blockade .
Facts & Assumptions
A special-vertex co-Bird-free comb admits an E-free structural partition supplies the following statement: Let be an -comb in a finite simple co-Bird-free graph , and let be outside all teeth and blocks, complete to every and anticomplete to every tooth. For every there exist disjoint sets with such that is -free, and has a partition into a nonempty ordered sequence of nonempty sets satisfying: the sequence is a pure blockade, its pattern is -free, and each individual vertex of every other comb block is pure to each . The blocks may additionally be chosen anticonnected.
Combs in a graph supplies the following definition: Let with , and let . An -comb in a graph is a sequence of pairs satisfying the conditions below. Here a vertex is complete to (respectively, anticomplete to) a set when the pair is complete (respectively, anticomplete) in the sense of def-edges-between-sets-and-pure-mixed-pairs. 1. is an -blockade; 2. the vertices are distinct; 3. the set is disjoint from every block ; and 4. for every , the vertex is complete to ; and 5. for all distinct , the vertex is anticomplete to . The vertices are the teeth of the comb.
The -graph and co- supplies the following definition: The -graph is the graph on vertices with edge set Thus is a five-vertex path and is a leaf attached to its middle vertex . The co- graph is the complement of this graph.
The Bird graph and co-Bird supplies the following definition: The Bird graph is the graph on vertices with edge set So spans the bull, and is a new leaf attached to the horn vertex . The co-Bird graph is the complement of the Bird graph.
Verification
Given: The graph, vertices, sets and hypotheses in the example.
The graph has only three vertices and hence cannot contain the six-vertex co-Bird. The single block is nonempty of size one, its tooth is outside it and complete to it, and is outside both and sees but misses . There are no distinct-tooth conditions to check.
The block contains no six-vertex , so its overlap support is empty. The singleton branch of the structural theorem gives exactly the displayed . The empty graph on and the one-vertex pattern contain no , the one-block blockade is pure, and the other-block purity condition is vacuous.
Depends on
Used by
Nothing in the library uses this result yet.
Dependency tree · two levels
11 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
- Huang–Ju–Zhou, Erdős–Hajnal beyond the five-vertex path, §6.2, Lemma 6.5, singleton boundary adaptation (standard reference, not scraped)