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.
In a special-vertex comb of a co--free graph, vertices in other comb blocks remain pure to every -overlap quotient block
Statement
Let be co--free and let be a comb with an outside vertex complete to all and anticomplete to all . Fix , form the nonempty -overlap blockade in , and form its iterated mixed quotients. Every vertex of is pure to every block of every iterate.
Facts & Assumptions
Given: The special-vertex comb, an index , and its iterated overlap quotients.
Relative to any nonadjacent pair complete to an induced in a co--free graph, every one-sided vertex is pure to that ; in particular, with , every external comb-block vertex is pure to every induced in (Relative to a complete nonedge pair in a co--free graph, every one-sided vertex is pure to an induced ).
Purity on every propagates to its overlap class (Purity on every induced propagates along an -overlap class).
For a blockade of connected blocks, suppose distinct mixed quotient blocks have outside vertices with a nonedge, complete to , and complete to and anticomplete to . If no vertex of is mixed on , there are mixed member blocks inside with an outside triple satisfying the same adjacency conditions (A quotient-level mixed-block witness descends to two mixed member blocks).
If an outside vertex is mixed on a connected set, it has opposite adjacency to the endpoints of some edge of that set (A vertex mixed on a connected set has opposite adjacency on some edge of that set).
In a co--free graph, if nonadjacent outside vertices are complete to an induced path , a vertex mixed on cannot have two consecutive nonneighbours on (Relative to a complete nonedge pair in a co--free graph, a one-sided vertex mixed on an induced path avoids two consecutive nonneighbours and three consecutive neighbours).
Initial overlap classes are connected, and taking a mixed quotient preserves connectedness of blocks (Every -overlap class is connected, A quotient block of connected or anticonnected blocks is again connected or anticonnected).
Each next iterate replaces mixed-reachability classes of blocks by their unions (The -overlap blockade and its iterated mixed quotients).
Proof
Write for iterate . For any external comb-block vertex , the comb and special-vertex hypotheses give , with nonadjacent and complete to . Thus [F1] makes pure to every induced in , and [F2] makes it pure to each block of .
All blocks of every are connected: start with the initial classes and repeatedly apply connectedness preservation in [F6].
Fix and assume the assertion for . Suppose an external vertex is mixed on a block of . By the induction hypothesis, each member block of inside is complete or anticomplete to , and both labels occur. By [F7], a mixed chain inside joins blocks of opposite labels; at a change of label, consecutive mixed blocks have complete to and anticomplete to .
Consider any mixed blocks at level with an outside triple satisfying: is a nonedge, are complete to , and is complete to and anticomplete to . No vertex is mixed on . Indeed, if one were, connectedness and [F4] give an edge in with an edge and a nonedge. Then is induced, are outside and complete to it, and is mixed on it with consecutive nonneighbours , contrary to [F5].
The pair in step 1.3 has the required triple at level . Whenever its current level exceeds one, apply [F3] to : step 1.2 supplies connected member blocks and step 2.1 supplies the directional no-mixed-vertex hypothesis. The resulting mixed blocks at level have an outside triple with all the same adjacency conditions. Repeating this finite descent reaches mixed initial classes and an outside triple with a nonedge, complete to , and complete to and anticomplete to . If , the initial pair already has these properties.
Apply step 2.1 to . Every vertex of is pure to . Since the pair is mixed, some vertex is complete to and some vertex is anticomplete to ; otherwise all vertices have the same label and the pair is pure. Therefore any is adjacent to and nonadjacent to , and is mixed on . Such a vertex exists because a blockade block is nonempty.
The vertices are outside , nonadjacent, and both complete to . Also . Apply [F1] with to every induced contained in , then [F2] to the overlap class . It follows that is pure to , contradicting step 4.1. Thus no external vertex is mixed on any block at level . Together with the base case this proves the assertion for every iterate.
Depends on
- Relative to a complete nonedge pair in a co-$E$-free graph, a one-sided vertex mixed on an induced path avoids two consecutive nonneighbours and three consecutive neighbours
- Relative to a complete nonedge pair in a co-$E$-free graph, every one-sided vertex is pure to an induced $H_5$
- Every $H_5$-overlap class is connected
- Purity on every induced $H_5$ propagates along an $H_5$-overlap class
- The $H_5$-overlap blockade and its iterated mixed quotients
- Iterated mixed quotients of an $H_5$-overlap blockade terminate at a pure blockade
- A vertex mixed on a connected set has opposite adjacency on some edge of that set
- A quotient block of connected or anticonnected blocks is again connected or anticonnected
- A quotient-level mixed-block witness descends to two mixed member blocks
- Combs in a graph
- The $E$-graph and co-$E$
- The graphs $H_0,H_1,\ldots,H_5$
- Edges between disjoint vertex sets; complete, anticomplete, pure and mixed pairs
Used by
Dependency tree · two levels
29 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, and Zhou, Erdős-Hajnal beyond the five-vertex path, Claim 6.4.3 (standard reference, not scraped)