PropositionStatement: 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.

Complementation preserves distinction of induced classes

PDF p. 2: Section 2, paragraph after Construction 1

Statement

Let $H_{1}, H_{2}$ be finite simple graphs with at least one vertex, and let $k$ be a positive integer. Then $R_{i n d}^{k} (H_{1}) \neq R_{i n d}^{k} (H_{2})$ if and only if $R_{i n d}^{k} (\overline{H_{1}}) \neq R_{i n d}^{k} (\overline{H_{2}})$ .

Here $\overline{H}$ has the same vertices as $H$ and precisely the edges between distinct vertices that are nonadjacent in $H$ . The class $R_{i n d}^{k} (H)$ consists of the nonempty finite simple graphs $G$ such that every function $V (G) \to {1, \dots, k}$ has a monochromatic induced copy of $H$ : an injective image on which both adjacency and nonadjacency agree with $H$ and all vertices have the same colour. Equality of these classes means equality of their membership predicates on such graphs.

Statement references

A finite simple graph is a finite vertex set together with a set of two-element vertex subsets

Induced vertex-Ramsey class

Order, size, complement and independence number

Facts & Assumptions

Given: Nonempty finite simple graphs $H_{1}, H_{2}$ and a positive integer $k$ .

Goal: Prove the stated equivalence of inequalities of induced vertex-Ramsey classes.

[F1]

A graph belongs to $R_{i n d}^{k} (H)$ exactly when every $k$ -colouring of its vertices contains a monochromatic induced copy of $H$ (Induced vertex-Ramsey class).

[F2]

Complementation preserves the vertex set and makes two distinct vertices adjacent exactly when they were nonadjacent (Order, size, complement and independence number).

[F3]

The same injection and vertex set transport monochromatic induced copies between $H$ in $G$ and $\overline{H}$ in $\overline{G}$ , and complementing twice returns the original finite simple graph (Complementation transports induced copies on fixed vertices).

Proof

technique · direct

1.1F1F2F3

Let $H$ and $G$ be nonempty finite simple graphs. They and their complements have the same respective vertex sets, so their vertex colourings are the same functions. For each such colouring, the induced-copy correspondence gives a monochromatic induced copy of $H$ in $G$ exactly when it gives one of $\overline{H}$ in $\overline{G}$ . Therefore $G \in R_{i n d}^{k} (H)$ if and only if $\overline{G} \in R_{i n d}^{k} (\overline{H})$ .

2.1givenstep 1.1

If the classes of $H_{1}$ and $H_{2}$ differ, some nonempty finite simple graph $G$ belongs to exactly one of them. Applying step 1.1 to both targets shows that $\overline{G}$ belongs to exactly one of the classes of $\overline{H_{1}}$ and $\overline{H_{2}}$ , so those classes differ.

3.1givenF2F3step 2.1∎

Conversely, if the classes of $\overline{H_{1}}$ and $\overline{H_{2}}$ differ, apply step 2.1 to those two nonempty finite simple graphs. Their complements are $H_{1}$ and $H_{2}$ , so the original classes differ. This proves both implications.

Extraction notes

The complement bars are preserved from the rendered PDF; the text extraction loses these bars.

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, Section 2, paragraph after Construction 1