Alphabeta Math
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.

Connected targets have repetition

PDF p. 2: Lemma 2.1, first proof paragraph

Statement

Let k≥1 and let H be connected. For every graph A and integer q≥1, A∈Rindk(H) implies qA∈Rindk(H), and a colouring of A avoiding a monochromatic induced H can be repeated on all copies to avoid one in qA. Thus H has the Ramsey repetition property at k.

Facts & Assumptions

[F1]

Graphs are finite, simple and nonempty. A k-colouring is a function to {1,…,k}; 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

[F2]

The graph qA has vertices (i,v) for 1≤i≤q and v∈V(A), with edges precisely between (i,u) and (i,v) when uv is an edge of A. Its tagged parts are induced copies of A with no edges between different parts. The disjoint multiple qA

[F3]

A graph belongs to Rindk(H) exactly when every k-colouring contains a monochromatic induced copy of H. The repetition property at k asserts this membership is equivalent for A and qA for every A and positive q. Induced vertex-Ramsey class Ramsey repetition property at fixed k

[F4]

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

[F5]

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 k, a connected graph H, a graph A, and a positive integer q.

Goal: Prove both membership implications and the stated construction of an avoiding colouring.

1.1F2F3F5given

Suppose A∈Rindk(H), and take any k-colouring of qA. Restrict it to the first tagged part and transport it to A by v↦(1,v). Membership of A gives a monochromatic induced embedding of H in A. Composing with that tagged-copy map gives a monochromatic induced copy in qA. Since the original colouring was arbitrary, qA∈Rindk(H).

1.2F1F2F3F4F5givenconstruct

Suppose instead that A∉Rindk(H). Choose a k-colouring c of A with no monochromatic induced copy of H, and colour every vertex (i,v) of qA by c(v). If this colouring had a monochromatic induced copy of H, connectivity would put all its vertices in one tagged part. Projecting that part by (i,v)↦v would give a monochromatic induced copy of H in A, contradicting the choice of c. Therefore the repeated colouring avoids such a copy and qA∉Rindk(H).

2.1F3step 1.1step 1.2∎

Step 1.2 proves the contrapositive of the implication from membership of qA to membership of A; step 1.1 proves the converse. Since A and q were arbitrary, their membership predicates are equivalent for every graph A and positive integer q. This is the Ramsey repetition property at k.

Depends on

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