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.
Disjoint-copy witness against repetition
PDF p. 2: Lemma 2.1, disconnected case, remaining sentences
Statement
Let be a finite simple graph with connected components , where , and let be a positive integer. Form their join . Let be a finite simple graph in with , and put . Such a graph exists, , and .
A connected component is a maximal connected subgraph; connected means that every two vertices are joined by a path. The join retains the internal edges of disjoint copies of the components and adds all edges between distinct copies. An independent set has no adjacent pair of distinct vertices, and is its maximum cardinality. A graph belongs to when every function from its vertices to has a monochromatic induced copy of ; such a copy is the image of an injection preserving and reflecting adjacency. The graph consists of disjoint copies of with no edges between them.
Statement references
Facts & Assumptions
For the stated , and , there exists with , and every such has no induced copy of and does not belong to (Independence gap for the join of components).
The components have nonempty, pairwise disjoint vertex sets covering ; each is induced on its vertex set, and there are no edges between distinct components. The join contains an induced copy of every component (Connected graphs and connected components defined by the existence of vertex paths, The connected components of a graph partition its vertex set and are its maximal connected subgraphs, Join of graphs).
In , the map identifies with the induced graph on the th tagged part; different parts are disjoint and have no edges between them (The disjoint multiple qA).
Restricting a colouring preserves the colours of the remaining vertices; composing induced embeddings produces an induced embedding and transports monochromaticity (Transport, restriction and relabelling of finite colourings).
If a set of more than elements is coloured with colours, at least of its elements have the same colour (Finite colour-class capacity and prescribed partitions).
An induced embedding is an injection that preserves and reflects adjacency between distinct vertices. Ramsey membership requires a monochromatic induced copy under every permitted colouring (Induced embeddings and induced copies of a graph, Induced vertex-Ramsey class).
Proof
Given: , its components, , , and as in the statement.
Goal: Prove the existence and nonmembership assertion for and show that every -colouring of contains a monochromatic induced copy of .
Fact F1 gives the existence of and, for every permitted choice of , gives . Fix such an and an arbitrary colouring .
For each , pull back along the tagged copy map to a -colouring of . Since , this colouring gives an induced embedding of whose image has one colour. Compose it with the tagged copy map; the resulting induced copy of lies in the th part and is monochromatic for . Choose one such copy and its colour for each of the finitely many indices.
Because , F5 gives distinct indices whose chosen copies of have the same colour. For each , restrict the induced embedding of in the th part to the component copy inside . This yields an induced embedding of in that part, and all of its image vertices have the common colour.
Define a map on by using the embedding selected for on . The component vertex sets partition , and the target parts are disjoint, so this map is well-defined and injective. Within a component it preserves and reflects adjacency; between different components there are no edges in and, because the target parts are distinct, no edges in . Thus the map is an induced embedding, and its image is monochromatic. As was arbitrary, .
Source notes
The article passage attributes the disconnected-case witness. The argument above derives it from the stated local and published suppliers.
Depends on
- Graph and colouring conventions
- Induced vertex-Ramsey class
- Join of graphs
- The disjoint multiple qA
- Independence gap for the join of components
- Finite colour-class capacity and prescribed partitions
- Transport, restriction and relabelling of finite colourings
- Connected graphs and connected components defined by the existence of vertex paths
- The connected components of a graph partition its vertex set and are its maximal connected subgraphs
- Induced embeddings and induced copies of a graph
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, Lemma 2.1, disconnected case, remaining sentences