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.

Construction 1 gives an induced vertex-Ramsey graph

PDF p. 2: Construction 1, monochromatic-hyperedge argument

Statement

Let $H$ be a finite simple graph with at least one vertex, and let $q \geq 3$ and $k \geq 1$ be integers. For any choices defining the graph $G = G (H, q, k)$ in Construction 1, every $k$ -colouring of $V (G)$ has a monochromatic hyperedge of the underlying hypergraph, and that hyperedge induces a copy of $H$ in $G$ . Consequently $G \in R_{i n d}^{k} (H)$ . Such construction choices exist for every stated $H, q, k$ .

Statement references

Graph and colouring conventions

Hypergraph terminology used in Construction 1

Construction 1: graph G(H,q,k)

Induced vertex-Ramsey class

Unrestricted finite colourings and used palettes

Weak hypergraph colourings with singleton boundary

Induced embeddings and induced copies of a graph

High-girth hypergraphs for Construction 1

Copies on hyperedges are induced

Facts & Assumptions

[F1]

By Construction 1: graph G(H,q,k), the underlying finite $∣ V (H) ∣$ -uniform hypergraph $H = (V, E)$ has Berge girth at least $q$ and no weak $k$ -colouring, and $V (G) = V$ . Each hyperedge $e$ is assigned a bijection $f_{e} : V (H) \to e$ . The construction and High-girth hypergraphs for Construction 1 supply choices for every stated $H, q, k$ , including the one-vertex case.

[F2]

By Unrestricted finite colourings and used palettes and Weak hypergraph colourings with singleton boundary, a $k$ -colouring is any function into ${1, \dots, k}$ , a subset is monochromatic when all its vertices receive the same colour, and such a function is a weak hypergraph colouring exactly when every hyperedge contains two vertices of different colours. Hypergraph and girth terminology is fixed by Hypergraph terminology used in Construction 1.

[F3]

By Copies on hyperedges are induced, each hyperedge $e$ induces the transported piece of $H$ , and $f_{e}$ is an induced embedding. An induced embedding preserves and reflects adjacency between distinct vertices, and its image induces a copy (Induced embeddings and induced copies of a graph). The graph and copy conventions are given in Graph and colouring conventions.

[F4]

By Induced vertex-Ramsey class, a nonempty finite simple graph belongs to $R_{i n d}^{k} (H)$ precisely when every function from its vertex set to ${1, \dots, k}$ has a monochromatic induced copy of $H$ .

Proof

Given: A graph $H$ , integers $q, k$ , and fixed construction choices as in the statement.

Goal: Prove the monochromatic-hyperedge assertion and the induced Ramsey membership, and account for the existence of the construction choices.

1.1givenF1F2choose

Let $c : V (G) \to {1, \dots, k}$ be arbitrary. Because $V (G) = V$ , it is also a colouring of the hypergraph's vertex set. It cannot be a weak $k$ -colouring, so some hyperedge $e$ fails the condition of containing two differently coloured vertices. Thus all vertices of $e$ have the same $c$ -colour. Since $∣ e ∣ = ∣ V (H) ∣ \geq 1$ , this is a nonempty monochromatic hyperedge.

2.1F1F3F4step 1.1∎

The induced subgraph of $G$ on $e$ is a copy of $H$ under $f_{e}$ , so it is monochromatic by step 1.1. In particular $G$ is nonempty. As $c$ was arbitrary, the defining condition for $G \in R_{i n d}^{k} (H)$ holds. The choices used above exist for every stated $H, q, k$ by F1. This proves all assertions.

Depends on

Used by · 3

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, Construction 1, monochromatic-hyperedge argument