LemmaStatement: AI-adaptedProof: AI-generated

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 Ramsey membership for H2

PDF p. 3: Section 3, final paragraph; PDF p. 4: Section 3, first paragraph

Statement

Use the recursive separator construction: $k \geq 2$ ; $H_{1}, H_{2}$ are non-isomorphic finite connected simple graphs, each with an edge, ordered by decreasing largest block order and then, in case of equality, by decreasing vertex order. A block is a maximal 2-connected subgraph or a bridge with its endpoints; its order is its number of vertices. The construction fixes an independent set $I$ of $H_{2}$ , its induced remainder $F = H_{2} - I$ , and a core graph $A$ such that every colouring of $V (A)$ with $k$ available colours has a monochromatic induced copy of $F$ . It defines $A_{1} = H_{2}$ and, for $2 \leq r \leq k$ , forms $A_{r}$ from a copy of $A$ and a disjoint copy of $A_{r - 1}$ for each chosen induced-copy vertex set of $F$ in $A$ and each $u \in I$ , with the prescribed neighbourhood attachments.

For $2 \leq r \leq k$ , if $A_{r - 1} \in R_{i n d}^{r - 1} (H_{2})$ , then $A_{r} \in R_{i n d}^{r} (H_{2})$ . Here membership in $R_{i n d}^{s} (H_{2})$ means that every function from the graph's vertex set to ${1, \dots, s}$ has a monochromatic induced copy of $H_{2}$ : an injective image preserving adjacency and nonadjacency whose vertices all have one colour. Colours need not all be used.

Statement references

Recursive graphs Ar and their attachments

Induced vertex-Ramsey class

Unrestricted finite colourings and used palettes

Facts & Assumptions

[F1]

Under the stated construction and $A_{r - 1} \in R_{i n d}^{r - 1} (H_{2})$ , if an attachment uses at most $r - 1$ colours under an $r$ -colouring of $A_{r}$ , it contains a monochromatic induced copy of $H_{2}$ , which remains induced in $A_{r}$ . An attachment using fewer colours supplies H2

[F2]

Under the stated construction, if every attachment uses all $r$ colours under an $r$ -colouring of $A_{r}$ , the core contains a monochromatic induced copy of $F$ and representatives of its colour from the corresponding attachments extend it to a monochromatic induced copy of $H_{2}$ in $A_{r}$ . A monochromatic F extends through all-colour attachments

[F3]

An $r$ -colouring is a function into ${1, \dots, r}$ ; an attachment uses exactly the colours in the image of its vertex set under that function. The induced Ramsey-class condition quantifies over every such function. Unrestricted finite colourings and used palettes Induced vertex-Ramsey class

Proof

Given: The recursive construction, $2 \leq r \leq k$ , and $A_{r - 1} \in R_{i n d}^{r - 1} (H_{2})$ .

Goal: Show that $A_{r} \in R_{i n d}^{r} (H_{2})$ .

1.1givenF1F3choose

Let $c : V (A_{r}) \to {1, \dots, r}$ be arbitrary. If some attachment does not use every colour in this palette, its used palette has at most $r - 1$ elements. By F1 it contains a monochromatic induced copy of $H_{2}$ that is also induced in $A_{r}$ .

2.1givenF2F3step 1.1∎

Otherwise every attachment uses all $r$ colours, including vacuously if there are no attachments. F2 then gives a monochromatic induced copy of $H_{2}$ in $A_{r}$ . Thus in either case the arbitrary colouring $c$ has such a copy. By the definition of the induced Ramsey class, $A_{r} \in R_{i n d}^{r} (H_{2})$ .

Depends on

Used by · 1

Invariant of the recursive induced separator

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, final paragraph; PDF p. 4, Section 3, first paragraph