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.
Mixed anticonnected blocks lift pattern obstructions to the ambient graph
Statement
Let be a finite graph, let , and let be pairwise disjoint nonempty sets. Assume:
- each is anticonnected;
- for each ; and
- for all distinct , either is complete to , or both is -sparse to and is -sparse to for some real .
Let be the graph on vertex set defined by
Then:
- if is a clique of size in , then contains an induced copy of the complement of the -subdivision of ;
- if is a graph on vertex set with and , and if , then contains an induced copy of with the vertex realized inside for every ;
- if is a graph on vertex set with , with distinguished vertices satisfying and , and if , then contains an induced copy of .
Facts & Assumptions
Given: The graph , the outside vertex , the disjoint sets , the parameter , and the auxiliary graph from the Statement.
If is anticonnected and , then is mixed on , so there exist nonadjacent such that and (A vertex mixed on an anticonnected set yields opposite adjacency on a nonedge).
A complete pair has all cross-edges, while a mixed pair is neither complete nor anticomplete (Edges between disjoint vertex sets; complete, anticomplete, pure and mixed pairs).
If is -sparse to , then every vertex of has at most neighbours in (Sparsity of one vertex set to another, and weak sparsity of a pair).
For adjacent distinguished vertices of , the graph is obtained by adjoining a new vertex adjacent exactly to and (The graphs and for two distinguished vertices).
Proof
For each , apply [L1] to choose nonadjacent vertices with and .
Now assume and . Choose arbitrarily. Suppose have been chosen with , so that for all one has if and only if .
Assume instead that , that , and that . Because for , choose and adjacent to . Since , the pair is complete, so . Suppose now that have been chosen with so that , for , and if and only if for all .
Let be a clique in . By definition of , the pairs are complete for all , so every vertex chosen from one selected block is adjacent to every vertex chosen from another selected block. Together with step 1.1, this shows that on the vertex set the only nonedges are and for . That is exactly the nonedge pattern of the complement of the -subdivision of , with as the complemented center, as the subdivision vertex, and as the corresponding leaf.
For each with , the pair is not complete, so hypothesis 3 and [L3] imply that has at most neighbours in . Therefore at most vertices of violate one of the required nonadjacency conditions to the previously chosen vertices. Since and , some vertex avoids all those forbidden sets. For such a choice, every required edge holds automatically because whenever the pair is complete.
By induction on , steps 1.2 and 2.2 produce vertices with if and only if for all distinct . Hence is an induced copy of . This proves assertion 2.
For , hypothesis 2 gives fewer than neighbours of in , so more than vertices of are nonadjacent to . As in step 2.2, the nonedge requirements to the previously chosen exclude at most further vertices. Hence some is simultaneously nonadjacent to and satisfies if and only if for every . Inducting on produces vertices such that the old vertices induce , the new vertex is adjacent exactly to and , and therefore is an induced copy of by [L4]. This proves assertion 3.
Depends on
- A vertex mixed on an anticonnected set yields opposite adjacency on a nonedge
- Anticonnected graphs and anticonnected components
- Sparsity of one vertex set to another, and weak sparsity of a pair
- Edges between disjoint vertex sets; complete, anticomplete, pure and mixed pairs
- The graphs $H^+$ and $H^-$ for two distinguished vertices
Used by
Dependency tree · two levels
12 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, proof of Lemma 2.1 and Claim 2.1.1 (standard reference, not scraped)