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.

Induced Ramsey graph with the same independence number

PDF p. 2: Section 2, second sentence after Construction 1

Statement

For every finite simple graph $H$ with at least one vertex and every positive integer $k$ , there is a finite simple graph $G \in R_{i n d}^{k} (H)$ with $α (G) = α (H)$ .

Here $R_{i n d}^{k} (H)$ consists of graphs in which every vertex colouring with colours $1, \dots, k$ has a monochromatic induced copy of $H$ . An induced copy preserves both adjacency and nonadjacency, and $α$ is the maximum size of a set of pairwise nonadjacent vertices.

Facts & Assumptions

[F1]

By Graph and colouring conventions and Induced vertex-Ramsey class, graphs in this statement are finite and simple, colourings are arbitrary functions into the indicated palette, and induced Ramsey membership means that every such colouring contains a monochromatic induced copy.

[F2]

By Order, size, complement and independence number and Cliques, independent sets, clique number and independence number, the complement $\overline{H}$ has the same vertices and reverses adjacency between distinct vertices. A clique is a set of pairwise adjacent vertices, and $ω (J)$ is the largest size of a clique in a finite graph $J$ .

[F3]

For any nonempty finite simple graph $J$ , $q \geq 3$ , and $k \geq 1$ , Construction 1 gives an induced vertex-Ramsey graph supplies a construction graph $R \in R_{i n d}^{k} (J)$ . By Construction 1: graph G(H,q,k), it is a realisation over a finite hypergraph of Berge girth at least $q$ whose pieces are copies of $J$ and whose edge set is the union of their edge sets. Each hyperedge induces a copy of $J$ by Construction 1 gives an induced vertex-Ramsey graph.

[F4]

By Small 2-connected subgraphs localise in high-girth pieces, an occurrence of a 2-connected graph with fewer than $q$ edges in such a realisation lies in one piece. A graph is 2-connected when it has at least three vertices, is connected, and remains connected after deletion of any vertex (Cutvertices, 2-connected pieces and nontrivial blocks). A graph is connected when its vertex set is nonempty and every two vertices are joined by a path (Connected graphs and connected components defined by the existence of vertex paths).

[F5]

By Complementation transports induced copies on fixed vertices, induced copies and their monochromatic vertex sets correspond under simultaneous complementation of target and host, and complementation is an involution. By Clique and independence duality under complementation, $α (\overline{R}) = ω (R)$ and $ω (\overline{H}) = α (H)$ .

[F6]

By The set [A]ᵏ of k-element subsets and the binomial coefficient C(n, k) := | [n]ᵏ|, $(\binom{n}{2})$ is the natural number counting the two-element subsets of an $n$ -element set. By The complete graph on an n-element vertex set has C(n, 2) edges, a complete graph on $n$ vertices has exactly $(\binom{n}{2})$ edges.

Proof

Given: A finite simple graph $H$ with at least one vertex and a positive integer $k$ .

Goal: Construct a graph in $R_{i n d}^{k} (H)$ whose independence number equals $α (H)$ .

1.1givenF2F3F6choose

Put $J = \overline{H}$ and $a = ω (J)$ . The graph $J$ is nonempty and finite, so $a \geq 1$ . Choose an integer $q \geq 3$ greater than $(\binom{a + 1}{2})$ , and choose a construction graph $R = G (J, q, k)$ as in F3. Then $R \in R_{i n d}^{k} (J)$ , and each piece is a copy of $J$ . Since an induced copy of $J$ occurs on a hyperedge, a maximum clique of $J$ gives a clique of size $a$ in $R$ . Thus $ω (R) \geq a$ .

2.1F2F3step 1.1

If $a = 1$ , $J$ has no edges: an edge would be a clique of size two. Every piece is therefore edgeless, and the union defining $R$ has no edges. Since $R$ contains a copy of the nonempty graph $J$ , it is nonempty, so $ω (R) = 1 = a$ .

2.2F2F3F4F6step 1.1

Suppose $a \geq 2$ and set $t = a + 1$ . If $R$ had a clique of size $t$ , its vertices and all their edges would form an ordinary subgraph $K_{t}$ . It has $(\binom{t}{2}) < q$ edges and is 2-connected: it is connected, has at least three vertices, and deleting any vertex leaves a connected complete graph. By F4 this occurrence would lie in a single piece. That piece is a copy of $J$ , which has no clique of size $a + 1$ , a contradiction. Hence $ω (R) \leq a$ , and together with step 1.1, $ω (R) = a$ .

3.1F1F2F5step 1.1step 2.1step 2.2∎

Let $G = \overline{R}$ . Any $k$ -colouring of $G$ is also a colouring of $R$ , since their vertex sets agree. Ramsey membership of $R$ gives a monochromatic induced copy of $J$ ; F5 transports it to a monochromatic induced copy of $\overline{J} = H$ in $G$ . Thus $G \in R_{i n d}^{k} (H)$ . In either case above, $α (G) = ω (R) = a = ω (\overline{H}) = α (H)$ by F5. This proves the proposition.

Source notes

The cited article states this consequence after Construction 1. The explicit clique bound and the separate edgeless case are supplied by the local argument above.

Depends on

Used by · 1

Independence gap for the join of components

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, second sentence after Construction 1