Recursive graphs Ar and their attachments

PDF p. 3: Section 3, paragraph beginning Next; PDF p. 3: Figure 1

Let $k\ge 2$ be an integer. Let $H_1,H_2$ be non-isomorphic finite connected simple graphs with edges, ordered so that $\beta (H_1)\ge \beta (H_2)$ and, in case of equality, $\mathrm{\mid }V(H_1)\mathrm{\mid }\ge \mathrm{\mid }V(H_2)\mathrm{\mid }$. A graph is connected if its vertex set is nonempty and every two vertices are joined by a path. A block is a maximal 2-connected subgraph, or a bridge with its endpoints; 2-connected means connected, with at least three vertices, and remaining connected after deletion of any vertex. A bridge is an edge whose deletion increases the number of connected components. For a graph with an edge, $\beta$ is the largest number of vertices in a block; for a nonempty edgeless graph it is $1$.

Fix an independent set $I$ of $H_2$ such that $F=H_2-I$ has $\beta (F)<\beta (H_2)$, and fix a finite simple graph $A$ containing no induced copy of $H_1$ and having the property that every vertex colouring with $k$ available colours contains a monochromatic induced copy of $F$. Independent means that no edge has both endpoints in $I$; $H_2-I$ is the graph induced on $V(H_2)\setminus I$. An induced copy of $F$ in $A$ is a subgraph $A[S]$ induced by a vertex set $S\subseteq V(A)$ for which there is an induced embedding $F\to A$ with image $S$: this is an injective vertex map preserving both adjacency and nonadjacency.

Fix bijections $V(H_2)\to h$ and $V(A)\to a$, where $h=\mathrm{\mid }V(H_2)\mathrm{\mid }$ and $a=\mathrm{\mid }V(A)\mathrm{\mid }$ are natural numbers regarded as finite ordinals. Transport the edges and $I$ along these bijections, and use $H_2,A,I,F$ for the resulting labelled objects. Thus $V(H_2)=h$ and $V(A)=a$. Use the natural-number order on these labels and its restrictions to $V(F)$ and $I$. Lists of equal length are compared lexicographically at their first unequal coordinate. For each vertex set $S$ inducing a copy of $F$ in $A$, choose the lexicographically least induced embedding ${\phi }_S:F\to A$ with image $S$, comparing its lists of images in the order of $V(F)$. Set $A_1=H_2$. For $2\le r\le k$, form a core that is a copy of $A$ and, for every such $S$ and every $u\in I$, a part $H_{{\phi }_S,u,r-1}$ that is a copy of $A_{r-1}$. The core and all parts are pairwise vertex-disjoint. Retain their internal edges. Join every vertex of $H_{{\phi }_S,u,r-1}$ to precisely those core vertices corresponding to ${\phi }_S(v)$ for which $v\in V(F)$ and $\{u,v\}\in E(H_2)$. Add no other edges.

To make the recursion deterministic, use the tagged core and parts of the labelled attachment construction, retaining only the parts indexed by the chosen ${\phi }_S$. Order the tagged vertices lexicographically: core vertices first in their $A$-label order, then parts by the image lists of ${\phi }_S$ and the label of $u$, and vertices within each part by their $A_{r-1}$ labels. Relabel this finite ordered vertex set by the unique order-preserving bijection onto its finite ordinal of the same size, transporting all edges and the names of the core and parts. The resulting labelled graph is $A_r$. Thus $A_r$ has exactly one part for each induced vertex-set copy of $F$ and each $u\in I$; its named core and parts retain the specified adjacencies after relabelling.

A finite simple graph is a finite vertex set together with a set of two-element vertex subsets

Subgraphs, induced subgraphs and spanning subgraphs

Graph isomorphisms, automorphisms and graph complements

Walks, closed walks, trails, paths and cycles, with length equal to the number of traversed edges

Connected graphs and connected components defined by the existence of vertex paths

The independent set I and remainder F

Existence of the base graph A

Neighbourhood attachments indexed by induced embeddings

Induced embeddings and induced copies of a graph

Injection, surjection, bijection

The natural numbers ℕ (von Neumann)

The cardinality | A| of a finite set

Order on the natural numbers

≤ is a linear order on ℕ

The well-ordering principle

The principle of mathematical induction

A subset of a finite set is finite, with | B| ≤ | A|, and equality holds if and only if B = A

The independent-remainder definition supplies an eligible fixed $I$ and nonempty $F$ under the stated hypotheses. The base-graph proposition supplies an eligible finite $A$ for this $k$. The induced-embedding definition gives exactly the maps used to identify induced copies, and the injection and bijection definitions specify the vertex maps and relabellings. The independent set I and remainder F Existence of the base graph A Induced embeddings and induced copies of a graph Injection, surjection, bijection

The natural numbers used as labels are the finite ordinals, and finite cardinality supplies the two initial bijections. Edge transport means replacing each edge by the pair of labels of its endpoints, so each labelling is a graph isomorphism and the chosen set and its induced remainder are transported with it. In particular, the labelled $H_2$ has vertex set exactly $h$ and is a finite simple graph in the domain of the graph-update recursion lemma. The natural-number order is a total order; its strict part is irreflexive, transitive and compares every two distinct labels. Its restrictions give the indicated orders on the finite sets $V(F)$ and $I$. The natural numbers ℕ (von Neumann) The cardinality | A| of a finite set Injection, surjection, bijection Graph isomorphisms, automorphisms and graph complements Order on the natural numbers ≤ is a linear order on ℕ

The following elementary finite-order argument supplies both least elements and relabellings. A strict total order means an irreflexive, transitive relation comparing each two distinct elements. In any nonempty finite strictly totally ordered set, take a bijective finite listing and scan it, retaining the smaller of the retained element and the next element. Induction on the number of entries scanned shows that the retained element is the least of all entries scanned, so the final element is the unique least element of the set. Now prove by induction on $n$ that each finite strictly totally ordered set $B$ of cardinality $n$ has a unique increasing bijection from $n$ onto $B$. For $n=0$ the empty map is the only map. For cardinality $n+1$, take the unique least element $b$. Swap its position with the last position in any bijective listing of $B$; deleting that last position gives a bijection from $n$ onto $B\setminus \{b\}$. Induction gives the unique increasing listing of this remainder. Prepending $b$ gives an increasing listing of $B$; any increasing listing must start with $b$, and its tail is the unique remainder listing, proving uniqueness. Taking the inverse gives the unique order-preserving bijection $B\to n$: an earlier element receives a smaller label. The arbitrary listings used in this existence argument do not affect the unique resulting maps. The cardinality | A| of a finite set Injection, surjection, bijection The principle of mathematical induction

Lexicographic comparison is a strict total order on lists of any fixed finite length. Distinct lists have a least differing coordinate by the well-ordering principle on their natural-number coordinate indices; the total order on labels then compares them uniquely. For transitivity, if $x{<}_{\mathrm{l}\mathrm{e}\mathrm{x}}y$ first differs at $p$ and $y{<}_{\mathrm{l}\mathrm{e}\mathrm{x}}z$ first differs at $q$, all three agree before $\min (p,q)$. If $p<q$, then $x_p<y_p=z_p$; if $q<p$, then $x_q=y_q<z_q$; if $p=q$, then $x_p<y_p<z_p$. Thus $x{<}_{\mathrm{l}\mathrm{e}\mathrm{x}}z$ in every case, and irreflexivity follows from the need for a differing coordinate. The length-zero case has only the empty list. The preceding finite-order argument lists $V(F)$ in increasing order. An embedding is determined by its image list in that order, so distinct embeddings have distinct lists. The attachment supplier gives a finite set of induced embeddings. For each induced image $S$, the embeddings having image $S$ form a nonempty subset, hence are finite. The finite-order argument therefore supplies its unique lexicographically least embedding ${\phi }_S$. Order on the natural numbers ≤ is a linear order on ℕ The well-ordering principle The principle of mathematical induction Induced embeddings and induced copies of a graph Neighbourhood attachments indexed by induced embeddings A subset of a finite set is finite, with | B| ≤ | A|, and equality holds if and only if B = A

For each finite labelled input $L$, including the graph with no vertices, the labelled neighbourhood-attachment construction has finitely many embedding-indexed parts and is a finite simple graph. The supplier identifies the graph using one chosen embedding per image as the induced subgraph on the core and the chosen parts. For part vertices the ordering keys are the image list of ${\phi }_S$, the label of $u$, and the label of the vertex of $L$. Distinct part vertices have distinct keys. The lexicographic argument orders these keys strictly and totally; ordering the core first in its label order extends this to a strict total order on all tagged vertices. The finite-order argument gives its unique order-preserving relabelling by its finite cardinality. Transporting edges along this bijection gives a unique finite simple graph with that finite ordinal as vertex set. Hence these rules give a total deterministic update on finite simple graphs with finite ordinal vertex sets. Applying finite-graph update recursion to the labelled $H_2$ and this update defines a unique finite labelled graph at every positive index, in particular through $k$; transporting the tags preserves the described core and attachments. No Ramsey property of $A_r$ is assumed here. Neighbourhood attachments indexed by induced embeddings A finite simple graph is a finite vertex set together with a set of two-element vertex subsets The cardinality | A| of a finite set Injection, surjection, bijection ≤ is a linear order on ℕ The principle of mathematical induction Recursion for deterministic finite graph updates