Alphabeta MathPersonal research
Colourings, embeddings and graph attachments
Develop finite colouring capacity, copy transport, graph operations and labelled attachments for ordinary Ramsey separation, repetition and the recursive induced separator.
1 · Prerequisites
- A finite simple graph is a finite vertex set together with a set of two-element vertex subsets
- Induced embeddings and induced copies of a graph
- Subgraphs, induced subgraphs and spanning subgraphs
- Cliques, independent sets, clique number and independence number
- Tagged graph families with anticomplete parts
- The Cartesian product A × B := { z ∈ P(P(A ∪ B)) : ∃ a ∈ A ∃ b ∈ B z = (a,b) }
- The product rule: | A × B| = | A| | B|, and |∏_i<m Aᵢ| = ∏_i<m| Aᵢ|
- A subset of a finite set is finite, with | B| ≤ | A|, and equality holds if and only if B = A
- The difference a ∖ b, the symmetric difference a △ b, and the complement X ∖ a relative to a set X
- Unrestricted finite colourings and used palettes
- Graph isomorphisms, automorphisms and graph complements
- A function is a relation f with (a,b) ∈ f and (a,c) ∈ f implying b = c; f : A → B, the value f(a), domain and codomain
- Injection, surjection, bijection
- Connected graphs and connected components defined by the existence of vertex paths
- Walks, closed walks, trails, paths and cycles, with length equal to the number of traversed edges
- Ordinary embeddings as injections preserving edges
- Connected subgraphs cannot cross anticomplete parts
2 · Logical flowchart
Arrows show item dependencies. A grouped prerequisite node points to items that use one or more of its members; their exact links are listed above.
3 · Items
Definition
Neighbourhood attachments indexed by induced embeddings
Lemma
One representative from each matching attachment reconstructs the target
Lemma