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.

Lemma 2.1: repetition characterizes connectivity

PDF p. 2: Lemma 2.1 and proof

Statement

Let $k \geq 1$ be an integer and let $H$ be a finite simple graph with at least one vertex. Then $H$ has the Ramsey repetition property at $k$ if and only if $H$ is connected.

Connected means that every two vertices of $H$ are joined by a path. The repetition property means that, for every finite simple nonempty graph $A$ and every integer $q \geq 1$ , $A \in R_{i n d}^{k} (H)$ if and only if $q A \in R_{i n d}^{k} (H)$ . Here $q A$ is the disjoint union of $q$ copies of $A$ , and membership in $R_{i n d}^{k} (H)$ means that every colouring of the graph's vertices with colours from ${1, \dots, k}$ contains a monochromatic induced copy of $H$ . An induced copy preserves both adjacency and nonadjacency, and monochromatic means that all its vertices have the same colour.

Statement references

Graph and colouring conventions

The disjoint multiple qA

Induced vertex-Ramsey class

Ramsey repetition property at fixed k

Connected graphs and connected components defined by the existence of vertex paths

Facts & Assumptions

[F1]

For a connected finite simple nonempty graph $H$ and positive integer $k$ , $H$ has the Ramsey repetition property at $k$ . Connected targets have repetition

[F2]

The connected components of a finite graph partition its vertex set. They are nonempty connected subgraphs; if the nonempty graph is disconnected, it has at least two components. Connected graphs and connected components defined by the existence of vertex paths The connected components of a graph partition its vertex set and are its maximal connected subgraphs

[F3]

If a finite simple graph $H$ has $t \geq 2$ connected components and $k$ is positive, there exist a finite simple graph $A$ and a positive integer $q$ such that $A \notin R_{i n d}^{k} (H)$ but $q A \in R_{i n d}^{k} (H)$ . Specifically, the witness lemma takes $q = k (t - 1) + 1$ and supplies an eligible $A$ . Disjoint-copy witness against repetition

[F4]

The repetition property requires the two membership predicates for $A$ and $q A$ to agree for every permitted $A$ and positive $q$ . Ramsey repetition property at fixed k

Proof

Given: A positive integer $k$ and a finite simple nonempty graph $H$ .

Goal: Show that $H$ has the repetition property at $k$ exactly when $H$ is connected.

1.1givenF1

If $H$ is connected, F1 applies to the given $H$ and $k$ , so $H$ has the repetition property at $k$ .

2.1givenF2F3F4step 1.1∎

If $H$ is disconnected, F2 gives $t \geq 2$ connected components. By F3, there are a permitted graph $A$ and positive integer $q$ for which $q A$ belongs to $R_{i n d}^{k} (H)$ but $A$ does not. This contradicts the universal equivalence required by F4, so $H$ does not have the repetition property. Thus the repetition property implies connectivity by contraposition; together with step 1.1, this proves the equivalence.

Depends on

Used by · 1

Reduction to connected targets

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 and proof