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.
Connected targets have repetition
PDF p. 2: Lemma 2.1, first proof paragraph
Statement
Let and let be connected. For every graph and integer , implies , and a colouring of avoiding a monochromatic induced can be repeated on all copies to avoid one in . Thus has the Ramsey repetition property at .
Statement references
Facts & Assumptions
Graphs are finite, simple and nonempty. A -colouring is a function to ; a copy is monochromatic when its vertices receive the same colour. An induced copy preserves both adjacency and nonadjacency. Graph and colouring conventions Unrestricted finite colourings and used palettes
The graph has vertices for and , with edges precisely between and when is an edge of . Its tagged parts are induced copies of with no edges between different parts. The disjoint multiple qA
A graph belongs to exactly when every -colouring contains a monochromatic induced copy of . The repetition property at asserts this membership is equivalent for and for every and positive . Induced vertex-Ramsey class Ramsey repetition property at fixed k
A connected graph is nonempty and has a path between every two vertices. The image of a connected graph under an induced embedding into a disjoint graph family lies in one tagged part. Connected graphs and connected components defined by the existence of vertex paths Connected subgraphs cannot cross anticomplete parts
Restriction preserves the colours of vertices, and composition of induced embeddings is induced and preserves monochromaticity under the transported colouring. Transport, restriction and relabelling of finite colourings
Proof
Given: A positive integer , a connected graph , a graph , and a positive integer .
Goal: Prove both membership implications and the stated construction of an avoiding colouring.
Suppose , and take any -colouring of . Restrict it to the first tagged part and transport it to by . Membership of gives a monochromatic induced embedding of in . Composing with that tagged-copy map gives a monochromatic induced copy in . Since the original colouring was arbitrary, .
Suppose instead that . Choose a -colouring of with no monochromatic induced copy of , and colour every vertex of by . If this colouring had a monochromatic induced copy of , connectivity would put all its vertices in one tagged part. Projecting that part by would give a monochromatic induced copy of in , contradicting the choice of . Therefore the repeated colouring avoids such a copy and .
Step 1.2 proves the contrapositive of the implication from membership of to membership of ; step 1.1 proves the converse. Since and were arbitrary, their membership predicates are equivalent for every graph and positive integer . This is the Ramsey repetition property at .
Depends on
- Graph and colouring conventions
- The disjoint multiple qA
- Induced vertex-Ramsey class
- Ramsey repetition property at fixed k
- Unrestricted finite colourings and used palettes
- Connected graphs and connected components defined by the existence of vertex paths
- Connected subgraphs cannot cross anticomplete parts
- Transport, restriction and relabelling of finite colourings
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, first proof paragraph