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.

An attachment using fewer colours supplies H2

PDF p. 3: Section 3, final paragraph

Statement

Use the hypotheses and notation of the recursive separator construction, with $2 \leq r \leq k$ . Thus $H_{2}$ and $A_{r - 1}$ are finite simple graphs and each attachment $H_{φ, u, r - 1}$ is a copy of $A_{r - 1}$ whose internal edges are retained in $A_{r}$ . Assume $A_{r - 1} \in R_{i n d}^{r - 1} (H_{2})$ : every function from $V (A_{r - 1})$ to ${1, \dots, r - 1}$ has a monochromatic induced copy of $H_{2}$ . In any function $c : V (A_{r}) \to {1, \dots, r}$ , if an attachment $H_{φ, u, r - 1}$ uses at most $r - 1$ colours, then that attachment contains a monochromatic induced copy of $H_{2}$ . Here an induced copy is the image of an injective vertex map preserving adjacency and nonadjacency; monochromatic means its image vertices have one common colour.

Statement references

Recursive graphs Ar and their attachments

Induced vertex-Ramsey class

Graph and colouring conventions

Unrestricted finite colourings and used palettes

Induced embeddings and induced copies of a graph

Injection, surjection, bijection

Facts & Assumptions

[F1]

The recursive construction makes each attachment a copy of $A_{r - 1}$ , retains its internal edges, and adds edges only between parts and the core. Thus its inclusion in $A_{r}$ is an induced embedding. Recursive graphs Ar and their attachments Induced embeddings and induced copies of a graph

[F2]

Membership in $R_{i n d}^{r - 1} (H_{2})$ means that every colouring of $V (A_{r - 1})$ by the available palette ${1, \dots, r - 1}$ has a monochromatic induced embedding of $H_{2}$ . Colours need not all be used. Induced vertex-Ramsey class Unrestricted finite colourings and used palettes

[F3]

A colouring with at most $r - 1$ used colours can be injectively relabelled into ${1, \dots, r - 1}$ without changing its monochromatic subsets. Composing induced embeddings gives an induced embedding, and restriction preserves the colours of its vertices. Transport, restriction and relabelling of finite colourings Injection, surjection, bijection

Proof

Given: The recursive construction, the Ramsey-class assumption, the colouring $c$ , and an attachment $B = H_{φ, u, r - 1}$ using at most $r - 1$ colours.

Goal: Find a monochromatic induced copy of $H_{2}$ inside $B$ .

1.1F1F3givenconstruct

Let $f : A_{r - 1} \to B$ be the graph isomorphism supplied by the copy construction. Pull the colouring back along $f$ , obtaining $d = c \circ f$ on $V (A_{r - 1})$ . Its used palette has at most $r - 1$ elements. Since $r - 1$ is positive, injectively relabel that palette into ${1, \dots, r - 1}$ to obtain a colouring $d^{'}$ with exactly the same monochromatic vertex subsets as $d$ .

2.1F1F2F3step 1.1given∎

By the Ramsey-class assumption applied to $d^{'}$ , there is an induced embedding $h : H_{2} \to A_{r - 1}$ whose image is monochromatic for $d^{'}$ , hence also for $d$ . The isomorphism $f$ is an induced embedding, so $f \circ h$ is an induced embedding into $B$ ; its image is monochromatic for $c$ by the definition of $d$ . Therefore $B$ contains the required copy. Its inclusion into $A_{r}$ also preserves the induced copy.

Depends on

Used by · 1

Inductive Ramsey membership for H2

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