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.

Independence gap for the join of components

PDF p. 2: Lemma 2.1, disconnected case, first three sentences

Statement

Let $H$ be a finite simple graph with connected components $H_{1}, \dots, H_{t}$ , where $t \geq 2$ , and let $k$ be a positive integer. Put $L = H_{1} \lor \dots \lor H_{t}$ . There is a finite simple graph $A \in R_{i n d}^{k} (L)$ with $α (A) = α (L)$ , and every such $A$ satisfies $α (A) = α (L) = \max_{i} α (H_{i}) < \sum_{i} α (H_{i}) = α (H)$ . Consequently $A$ contains no induced copy of $H$ and $A \notin R_{i n d}^{k} (H)$ .

Here a connected component is a maximal connected subgraph, and a connected graph has a path between every pair of its vertices. The join is formed from disjoint copies of the $H_{i}$ by retaining their internal edges and adding all edges between distinct copies. An independent set has no adjacent pair of distinct vertices, and $α$ is its maximum cardinality. The class $R_{i n d}^{k} (J)$ consists of graphs in which every vertex colouring with colours $1, \dots, k$ has a monochromatic induced copy of $J$ ; an induced copy preserves both adjacency and nonadjacency.

Statement references

Graph and colouring conventions

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

Walks, closed walks, trails, paths and cycles, with length equal to the number of traversed edges

Join of graphs

Order, size, complement and independence number

Induced vertex-Ramsey class

Facts & Assumptions

[F1]

The connected components of a graph have nonempty, pairwise disjoint vertex sets covering its vertices, and each component is the induced graph on its vertex set. A component is a reachability class: adjacent vertices are connected by a path of one edge. See The connected components of a graph partition its vertex set and are its maximal connected subgraphs, Connected graphs and connected components defined by the existence of vertex paths, and Walks, closed walks, trails, paths and cycles, with length equal to the number of traversed edges.

[F2]

The tagged disjoint union has a copy of each graph as a part and no edges between different parts; the join retains the part edges and makes distinct parts completely adjacent. See Tagged graph families with anticomplete parts and Join of graphs.

[F3]

For nonempty finite simple graphs, the independence number of their tagged disjoint union is the sum of their independence numbers, and that of their complete join is their maximum. If there are at least two parts, the maximum is strictly smaller than the sum. See Independence numbers of disjoint families and complete joins.

[F4]

For every nonempty finite simple graph $J$ and positive integer $k$ , there is a finite induced $k$ -colour Ramsey graph $B$ for $J$ with $α (B) = α (J)$ . See Induced Ramsey graph with the same independence number.

[F5]

If $J$ has an induced embedding into a finite simple graph $G$ , then $α (J) \leq α (G)$ . An induced copy yields such an embedding. See Independence is monotone under induced embeddings.

[F6]

Induced Ramsey membership requires a monochromatic induced copy for every colouring $V (G) \to {1, \dots, k}$ ; colourings need not use every colour. See Induced vertex-Ramsey class.

Proof

Given: A finite simple graph $H$ with components $H_{1}, \dots, H_{t}$ , where $t \geq 2$ , and a positive integer $k$ .

Goal: Establish the existence and independence gap for $A$ , and exclude $A$ from the induced Ramsey class of $H$ .

1.1givenF1F2

By F1, the component vertex sets partition $V (H)$ , and no edge of $H$ joins distinct components: such an edge would be a path joining their endpoints. Thus the map sending each vertex $v$ of the $i$ th component to its tagged vertex $(i, v)$ is an isomorphism from $H$ to the tagged disjoint union of the $H_{i}$ . It preserves and reflects adjacency, so it sends independent sets bijectively to independent sets of the same size; consequently the two graphs have the same independence number.

2.1givenF1F2F3F4step 1.1

Each $H_{i}$ is nonempty by F1. Applying F3 to these components and using the isomorphism in step 1.1 gives $α (H) = \sum_{i} α (H_{i})$ . By the definition of $L$ and F3, $α (L) = \max_{i} α (H_{i}) < \sum_{i} α (H_{i})$ . The graph $L$ is finite, simple and nonempty, so F4 supplies an $A \in R_{i n d}^{k} (L)$ with $α (A) = α (L)$ . These equalities and the strict inequality hold for every such $A$ .

3.1givenF5F6step 2.1∎

If such an $A$ contained an induced copy of $H$ , F5 would give $α (H) \leq α (A)$ , contradicting step 2.1. Hence it has no induced copy of $H$ . The constant colouring of $V (A)$ with colour $1$ is permitted because $k \geq 1$ ; it has no monochromatic induced copy of $H$ . By F6, $A \notin R_{i n d}^{k} (H)$ . This proves the lemma.

Source notes

The cited article passage attributes the displayed disconnected-case conclusion. The argument above uses the listed local suppliers.

Depends on

Used by · 1

Disjoint-copy witness against repetition

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, disconnected case, first three sentences