Alphabeta Math
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.

The k=1 case

PDF p. 2: Section 3, opening paragraph and repeated ordinary case

Statement

Let H1,H2 be non-isomorphic finite simple graphs, each with at least one vertex. Their ordinary one-colour vertex-Ramsey classes are distinct, R1(H1)≠R1(H2), and their induced one-colour vertex-Ramsey classes are distinct, Rind1(H1)≠Rind1(H2). Moreover, for each i∈{1,2}, Hi∈R1(Hi) and Hi∈Rind1(Hi).

Here an ordinary copy of a graph is a subgraph isomorphic to it, while an induced copy includes all host edges between its vertices. A one-colour vertex-Ramsey class consists of the nonempty finite simple graphs in which every function from the vertex set to {1} has a monochromatic copy of the specified kind. Non-isomorphic means that no vertex bijection preserves and reflects adjacency.

Facts & Assumptions

[F1]

An ordinary embedding is an injective vertex map preserving edges and exists exactly when the host contains an ordinary copy. An induced embedding is an injective vertex map preserving and reflecting adjacency, and its image is an induced copy. Hence every induced embedding is an ordinary embedding (Ordinary embeddings as injections preserving edges, Induced embeddings and induced copies of a graph).

[F2]

For nonempty finite simple graphs H,G, membership of G in R1(H), respectively Rind1(H), means that every function V(G)→{1} has a monochromatic ordinary, respectively induced, copy of H (Ordinary vertex-Ramsey class, Induced vertex-Ramsey class).

[F3]

If two finite simple graphs admit ordinary embeddings in both directions, they are isomorphic (Rigidity of mutual ordinary embeddings).

Proof

Given: Non-isomorphic finite simple graphs H1,H2, each with at least one vertex.

Goal: Prove both class inequalities and the two self-memberships for each graph.

1.1givenF1F2

For any nonempty finite simple graph G, there is exactly one function V(G)→{1}, and it is constant. Consequently every copy in G is monochromatic for that function. By the membership definitions, G∈R1(H) exactly when G contains an ordinary copy of H, and G∈Rind1(H) exactly when G contains an induced copy of H. In particular, the identity vertex map gives both an ordinary and an induced copy of Hi in itself, proving both self-memberships for each i.

2.1givenF1F3step 1.1choose∎

By finite mutual-embedding rigidity and non-isomorphism, at least one of the ordinary embeddings H1→H2 and H2→H1 does not exist. Choose indices a,b with {a,b}={1,2} such that Ha has no ordinary embedding into Hb. Then Hb contains neither an ordinary nor an induced copy of Ha: an induced embedding would also be an ordinary embedding. Thus Hb belongs to both one-colour classes of Hb but to neither corresponding class of Ha. The same graph therefore distinguishes each pair of classes, establishing both inequalities.

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