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 case
PDF p. 2: Section 3, opening paragraph and repeated ordinary case
Statement
Let be non-isomorphic finite simple graphs, each with at least one vertex. Their ordinary one-colour vertex-Ramsey classes are distinct, , and their induced one-colour vertex-Ramsey classes are distinct, . Moreover, for each , and .
Here an ordinary copy of a graph is a subgraph isomorphic to it, while an induced copy includes all host edges between its vertices. A one-colour vertex-Ramsey class consists of the nonempty finite simple graphs in which every function from the vertex set to has a monochromatic copy of the specified kind. Non-isomorphic means that no vertex bijection preserves and reflects adjacency.
Statement references
Facts & Assumptions
An ordinary embedding is an injective vertex map preserving edges and exists exactly when the host contains an ordinary copy. An induced embedding is an injective vertex map preserving and reflecting adjacency, and its image is an induced copy. Hence every induced embedding is an ordinary embedding (Ordinary embeddings as injections preserving edges, Induced embeddings and induced copies of a graph).
For nonempty finite simple graphs , membership of in , respectively , means that every function has a monochromatic ordinary, respectively induced, copy of (Ordinary vertex-Ramsey class, Induced vertex-Ramsey class).
If two finite simple graphs admit ordinary embeddings in both directions, they are isomorphic (Rigidity of mutual ordinary embeddings).
Proof
Given: Non-isomorphic finite simple graphs , each with at least one vertex.
Goal: Prove both class inequalities and the two self-memberships for each graph.
For any nonempty finite simple graph , there is exactly one function , and it is constant. Consequently every copy in is monochromatic for that function. By the membership definitions, exactly when contains an ordinary copy of , and exactly when contains an induced copy of . In particular, the identity vertex map gives both an ordinary and an induced copy of in itself, proving both self-memberships for each .
By finite mutual-embedding rigidity and non-isomorphism, at least one of the ordinary embeddings and does not exist. Choose indices with such that has no ordinary embedding into . Then contains neither an ordinary nor an induced copy of : an induced embedding would also be an ordinary embedding. Thus belongs to both one-colour classes of but to neither corresponding class of . The same graph therefore distinguishes each pair of classes, establishing both inequalities.
Depends on
Dependency tree · 2 levels
Each result is drawn at its shortest distance from this item. Arrows run from prerequisites to the items that use them; this item has a heavier outline. External source nodes link directly to the cited text. The view shows up to two dependency steps; open a prerequisite to continue.
Sources
- Maria Axenovich and Patrick Schmitteckert, Non-isomorphic graphs have distinct vertex-Ramsey classes, arXiv:2610.03704v1 · PDF p. 2, Section 3, opening paragraph and repeated ordinary case