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

Inductive colouring avoiding H1

PDF p. 3: Section 3, paragraph beginning We have that

Statement

Use the recursive graphs A1,…,Ak and their base graph A from Recursive graphs Ar and their attachments. In particular, k≥2, H1 is a finite connected simple graph with an edge, A contains no induced copy of H1, and for 2≤r≤k the graph Ar consists of a core isomorphic to A and pairwise disjoint attachment parts, each inducing a copy of Ar−1, with no edges between distinct parts. An induced copy is the image of an injective vertex map preserving and reflecting adjacency.

If 2≤r≤k and Ar−1∉Rindr−1(H1), then Ar∉Rindr(H1). More precisely, colour the core with colour 1 and each attachment with colours 2,…,r so that it has no monochromatic induced copy of H1; the resulting r-colouring has no monochromatic induced copy of H1.

Here an s-colouring is a function from the vertex set to {1,…,s}; it need not use every colour. A set is monochromatic when all its vertices have the same colour. The induced s-colour vertex-Ramsey class of H1 consists of the nonempty finite simple graphs for which every s-colouring contains a monochromatic induced copy of H1.

Facts & Assumptions

[F1]

The recursive construction gives a finite graph Ar whose core induces a copy of A, whose attachment parts induce copies of Ar−1, and which has no edges between distinct attachment parts. The base A has no induced copy of H1, and H1 is nonempty and connected. Recursive graphs Ar and their attachments Connected graphs and connected components defined by the existence of vertex paths

[F2]

Nonmembership of a nonempty finite graph in Rinds(H1) means that some s-colouring has no monochromatic induced copy of H1. Colours are labels and need not all occur. Induced vertex-Ramsey class Unrestricted finite colourings and used palettes

[F3]

An induced embedding preserves and reflects adjacency. A graph isomorphism is a bijection of vertex sets preserving and reflecting adjacency; its inverse has the same property. Transport along an isomorphism and injective relabelling of colours preserve monochromatic induced copies. Induced embeddings and induced copies of a graph Graph isomorphisms, automorphisms and graph complements Transport, restriction and relabelling of finite colourings

[F4]

If a graph is partitioned into a base and pairwise anticomplete attachment parts, the base has a fixed colour unused on the attachments, the base contains no induced copy of a nonempty connected target, and every attachment avoids monochromatic induced copies of that target, then the whole colouring avoids them. Avoidance using separated palettes and anticomplete attachments

[F5]

In the recursive setup, H2 has an edge, I is independent in H2, F=H2−I, and every k-colouring of A contains a monochromatic induced copy of F. Also A1=H2, and every Aj with 2≤j≤k contains a core isomorphic to A. Recursive graphs Ar and their attachments

[F6]

Deleting an independent set from a finite simple graph with an edge leaves a nonempty finite induced graph. Nonempty remainder after deleting an independent set

Proof

Given: The recursive construction, 2≤r≤k, and Ar−1∉Rindr−1(H1).

Goal: Construct the stated r-colouring of Ar and show that it avoids a monochromatic induced H1.

1.1givenF1F2F3F5F6

Applying F6 to H2 and I shows that F is nonempty. The constant assignment c(v)=1 on V(A) is a k-colouring, even if V(A) were empty, since k≥2 and colours need not all occur. By the property of A in F5 this colouring contains an induced copy of F. Its embedding maps a vertex of F to a vertex of A, so A is nonempty. Now A1=H2 is nonempty because it has an edge, and for every 2≤j≤k the core in Aj is nonempty because its vertex set is in bijection with V(A). Thus all Aj, in particular Ar−1 and Ar, are nonempty finite graphs.

2.1givenF1F2F3step 1.1

By step 1.1, Ar−1 is nonempty, so by nonmembership choose an (r−1)-colouring of Ar−1 with no monochromatic induced copy of H1. For each attachment, transport this colouring through an isomorphism from Ar−1 onto that part and relabel each colour i as i+1. The relabelling is injective and takes values in {2,…,r}. A monochromatic induced H1 in a transported part would pull back through the inverse isomorphism to one in Ar−1, and injective relabelling cannot create monochromaticity. Thus every attachment avoids such a copy.

3.1F1F2F3F4step 1.1step 2.1∎

Give every core vertex colour 1. The core and attachment parts are disjoint and cover V(Ar), so these assignments form an r-colouring. The core has no induced H1, since it is isomorphic to A; distinct attachments have no edges between them, and colour 1 is absent from every attachment. Applying the connected-target avoidance fact to this partition and the colourings from step 2.1 shows that Ar has no monochromatic induced copy of H1. Since Ar is nonempty by step 1.1, the definition of the induced Ramsey class therefore gives Ar∉Rindr(H1).

Depends on

Used by · 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