ExampleConstruction: AI-adaptedVerification: 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.

Join separator for equal-order targets

PDF p. 2: Section 3, ordinary classes, equal-order case

Example

Let $H_{1}$ and $H_{2}$ be finite simple graphs of the same order $n \geq 1$ , and suppose that $H_{2}$ contains no ordinary copy of $H_{1}$ . Let $k \geq 2$ be an integer. Form $G = H_{2} \lor K_{(k - 1) (n - 1)}$ using disjoint parts. Then $G \in R^{k} (H_{2}) ∖ R^{k} (H_{1})$ . In particular, any two non-isomorphic finite simple graphs of equal positive order can be labelled so that this construction separates their classes in that direction.

Here graph order means the number of vertices. An ordinary copy is a subgraph isomorphic to the target; extra host edges between its vertices are allowed. The join retains the edges within its parts and adds every cross-edge. The graph $K_{m}$ is complete on $m$ vertices, including the empty graph when $m = 0$ . A $k$ -colouring is a function from the vertex set to ${1, \dots, k}$ ; a copy is monochromatic when all its vertices have the same colour. The class $R^{k} (H)$ consists of hosts for which every such colouring has a monochromatic ordinary copy of $H$ .

Facts & Assumptions

[F1]

For a finite simple graph of order $n \geq 1$ and integer $k \geq 2$ , every $k$ -colouring of its join with $K_{(k - 1) (n - 1)}$ has a monochromatic ordinary copy of that graph (Completion inside the join separator).

[F2]

If a finite set has at most $a b$ elements, where $a, b \geq 1$ are integers, it admits an $a$ -colouring with every colour class of size at most $b$ (Finite colour-class capacity and prescribed partitions).

[F3]

In a join the designated parts are disjoint, the first part induces a copy of its original graph, and the second part has the stated number of vertices. A copy has as many vertices as its target (Join of graphs, Graph and colouring conventions, Order, size, complement and independence number).

[F4]

A colouring may leave colours unused. A host belongs to $R^{k} (H)$ exactly when every $k$ -colouring has a monochromatic ordinary copy of $H$ (Unrestricted finite colourings and used palettes, Ordinary vertex-Ramsey class).

[F5]

Two non-isomorphic finite simple graphs of equal positive order can be labelled so that the second contains no ordinary copy of the first (Orienting equal-order non-isomorphic targets).

Verification

Given: The graphs $H_{1}, H_{2}$ , their common order $n$ , the integer $k$ , and the join $G$ in the example.

Goal: Prove the two class-membership assertions and the final orientation claim.

1.1givenF1F4

Apply the join completion fact to $H_{2}$ . Every $k$ -colouring of $G$ contains a monochromatic ordinary copy of $H_{2}$ , so $G \in R^{k} (H_{2})$ .

1.2givenF2F3F4construct

Colour every vertex in the $H_{2}$ part with colour $1$ . If $n \geq 2$ , apply the finite capacity fact to the clique part with $a = k - 1$ and $b = n - 1$ , then relabel its $a$ colours as $2, \dots, k$ . Thus each of those colour classes has at most $n - 1$ vertices. If $n = 1$ , the clique part is empty and the same conclusion holds with all those colours unused. This gives a $k$ -colouring of all of $G$ .

2.1givenF3F4step 1.1step 1.2

A monochromatic copy of $H_{1}$ in colour $1$ would lie entirely in the $H_{2}$ part, where no such copy exists. A monochromatic copy in any other colour would require $n$ vertices, but that colour class has at most $n - 1$ . Thus this colouring has no monochromatic copy of $H_{1}$ , and $G \notin R^{k} (H_{1})$ . Together with step 1.1 this proves the displayed separation.

3.1F5step 2.1∎

For two non-isomorphic finite simple graphs of the same positive order, choose labels as in the orientation fact. Their labelled pair satisfies the hypotheses already used, so the same construction separates the classes in the stated direction.

Depends on

Used by · 1

Ordinary part of Theorem 1.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

Maria Axenovich and Patrick Schmitteckert, Non-isomorphic graphs have distinct vertex-Ramsey classes, arXiv:2610.03704v1 · PDF p. 2, Section 3, ordinary classes, equal-order case