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.
Inductive colouring avoiding H1
PDF p. 3: Section 3, paragraph beginning We have that
Statement
Use the recursive graphs and their base graph from Recursive graphs Ar and their attachments. In particular, , is a finite connected simple graph with an edge, contains no induced copy of , and for the graph consists of a core isomorphic to and pairwise disjoint attachment parts, each inducing a copy of , with no edges between distinct parts. An induced copy is the image of an injective vertex map preserving and reflecting adjacency.
If and , then . More precisely, colour the core with colour and each attachment with colours so that it has no monochromatic induced copy of ; the resulting -colouring has no monochromatic induced copy of .
Here an -colouring is a function from the vertex set to ; it need not use every colour. A set is monochromatic when all its vertices have the same colour. The induced -colour vertex-Ramsey class of consists of the nonempty finite simple graphs for which every -colouring contains a monochromatic induced copy of .
Facts & Assumptions
The recursive construction gives a finite graph whose core induces a copy of , whose attachment parts induce copies of , and which has no edges between distinct attachment parts. The base has no induced copy of , and is nonempty and connected. Recursive graphs Ar and their attachments Connected graphs and connected components defined by the existence of vertex paths
Nonmembership of a nonempty finite graph in means that some -colouring has no monochromatic induced copy of . Colours are labels and need not all occur. Induced vertex-Ramsey class Unrestricted finite colourings and used palettes
An induced embedding preserves and reflects adjacency. A graph isomorphism is a bijection of vertex sets preserving and reflecting adjacency; its inverse has the same property. Transport along an isomorphism and injective relabelling of colours preserve monochromatic induced copies. Induced embeddings and induced copies of a graph Graph isomorphisms, automorphisms and graph complements Transport, restriction and relabelling of finite colourings
If a graph is partitioned into a base and pairwise anticomplete attachment parts, the base has a fixed colour unused on the attachments, the base contains no induced copy of a nonempty connected target, and every attachment avoids monochromatic induced copies of that target, then the whole colouring avoids them. Avoidance using separated palettes and anticomplete attachments
In the recursive setup, has an edge, is independent in , , and every -colouring of contains a monochromatic induced copy of . Also , and every with contains a core isomorphic to . Recursive graphs Ar and their attachments
Deleting an independent set from a finite simple graph with an edge leaves a nonempty finite induced graph. Nonempty remainder after deleting an independent set
Proof
Given: The recursive construction, , and .
Goal: Construct the stated -colouring of and show that it avoids a monochromatic induced .
Applying F6 to and shows that is nonempty. The constant assignment on is a -colouring, even if were empty, since and colours need not all occur. By the property of in F5 this colouring contains an induced copy of . Its embedding maps a vertex of to a vertex of , so is nonempty. Now is nonempty because it has an edge, and for every the core in is nonempty because its vertex set is in bijection with . Thus all , in particular and , are nonempty finite graphs.
By step 1.1, is nonempty, so by nonmembership choose an -colouring of with no monochromatic induced copy of . For each attachment, transport this colouring through an isomorphism from onto that part and relabel each colour as . The relabelling is injective and takes values in . A monochromatic induced in a transported part would pull back through the inverse isomorphism to one in , and injective relabelling cannot create monochromaticity. Thus every attachment avoids such a copy.
Give every core vertex colour . The core and attachment parts are disjoint and cover , so these assignments form an -colouring. The core has no induced , since it is isomorphic to ; distinct attachments have no edges between them, and colour is absent from every attachment. Applying the connected-target avoidance fact to this partition and the colourings from step 2.1 shows that has no monochromatic induced copy of . Since is nonempty by step 1.1, the definition of the induced Ramsey class therefore gives .
Depends on
- Recursive graphs Ar and their attachments
- Induced vertex-Ramsey class
- Unrestricted finite colourings and used palettes
- Avoidance using separated palettes and anticomplete attachments
- Transport, restriction and relabelling of finite colourings
- Connected graphs and connected components defined by the existence of vertex paths
- Induced embeddings and induced copies of a graph
- Graph isomorphisms, automorphisms and graph complements
- Nonempty remainder after deleting an independent set
Used by · 1
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. 3, Section 3, paragraph beginning We have that