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.

Disjoint-copy witness against repetition

PDF p. 2: Lemma 2.1, disconnected case, remaining sentences

Statement

Let H be a finite simple graph with connected components H1,…,Ht, where t≥2, and let k be a positive integer. Form their join L=H1∨⋯∨Ht. Let A be a finite simple graph in Rindk(L) with α(A)=α(L), and put q=k(t−1)+1. Such a graph A exists, A∉Rindk(H), and qA∈Rindk(H).

A connected component is a maximal connected subgraph; connected means that every two vertices are joined by a path. The join retains the internal edges of disjoint copies of the components and adds all edges between distinct copies. An independent set has no adjacent pair of distinct vertices, and α is its maximum cardinality. A graph belongs to Rindk(J) when every function from its vertices to {1,…,k} has a monochromatic induced copy of J; such a copy is the image of an injection preserving and reflecting adjacency. The graph qA consists of q disjoint copies of A with no edges between them.

Facts & Assumptions

[F1]

For the stated H, L and k, there exists A∈Rindk(L) with α(A)=α(L), and every such A has no induced copy of H and does not belong to Rindk(H) (Independence gap for the join of components).

[F2]

The components have nonempty, pairwise disjoint vertex sets covering V(H); each is induced on its vertex set, and there are no edges between distinct components. The join contains an induced copy of every component (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, Join of graphs).

[F3]

In qA, the map v↦(i,v) identifies A with the induced graph on the ith tagged part; different parts are disjoint and have no edges between them (The disjoint multiple qA).

[F4]

Restricting a colouring preserves the colours of the remaining vertices; composing induced embeddings produces an induced embedding and transports monochromaticity (Transport, restriction and relabelling of finite colourings).

[F5]

If a set of more than k(t−1) elements is coloured with k colours, at least t of its elements have the same colour (Finite colour-class capacity and prescribed partitions).

[F6]

An induced embedding is an injection that preserves and reflects adjacency between distinct vertices. Ramsey membership requires a monochromatic induced copy under every permitted colouring (Induced embeddings and induced copies of a graph, Induced vertex-Ramsey class).

Proof

Given: H, its components, k, L, A and q as in the statement.

Goal: Prove the existence and nonmembership assertion for A and show that every k-colouring of qA contains a monochromatic induced copy of H.

1.1givenF1F6

Fact F1 gives the existence of A and, for every permitted choice of A, gives A∉Rindk(H). Fix such an A and an arbitrary colouring c:V(qA)→{1,…,k}.

1.2givenF3F4F6construct

For each i∈{1,…,q}, pull c back along the tagged copy map v↦(i,v) to a k-colouring of A. Since A∈Rindk(L), this colouring gives an induced embedding of L whose image has one colour. Compose it with the tagged copy map; the resulting induced copy of L lies in the ith part and is monochromatic for c. Choose one such copy and its colour for each of the finitely many indices.

2.1givenF2F4F5step 1.2choose

Because q=k(t−1)+1>k(t−1), F5 gives distinct indices i1,…,it whose chosen copies of L have the same colour. For each j, restrict the induced embedding of L in the ijth part to the component copy Hj inside L. This yields an induced embedding of Hj in that part, and all of its image vertices have the common colour.

3.1givenF2F3F6step 2.1construct∎

Define a map on V(H) by using the embedding selected for Hj on V(Hj). The component vertex sets partition V(H), and the target parts are disjoint, so this map is well-defined and injective. Within a component it preserves and reflects adjacency; between different components there are no edges in H and, because the target parts are distinct, no edges in qA. Thus the map is an induced embedding, and its image is monochromatic. As c was arbitrary, qA∈Rindk(H).

Source notes

The article passage attributes the disconnected-case witness. The argument above derives it from the stated local and published suppliers.

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