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 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
- 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
- Injection, surjection, bijection
- Induced embeddings and induced copies of a graph
- 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ᵢ|
- The sum rule: a finite disjoint union is finite with | A ∪ B| = | A| + | B| and |⋃_i ∈ I Aᵢ| = ∑_i ∈ I| Aᵢ|, and a sum over a finite index set splits along a partition
- An indexed family (Aᵢ)_i ∈ I is a function with domain I; {Aᵢ : i ∈ I} is its range
- (a,b) = (c,d) if and only if a = c and b = d
- A subset of a finite set is finite, with | B| ≤ | A|, and equality holds if and only if B = A
- Adjacency, incidence, open and closed neighbourhoods, vertex degree, minimum degree and maximum degree
- Cliques, independent sets, clique number and independence number
- The cardinality | A| of a finite set
- The recursion theorem
- The principle of mathematical induction
- The von Neumann naturals form a Peano system
- The natural numbers ℕ (von Neumann)
- The power set P(x) = { z : z ⊆ x }
- The Axiom Schema of Separation: for each formula φ, ∀ p̄ ∀ x ∃ y ∀ z (z ∈ y ↔ (z ∈ x ∧ φ(z,p̄)))
- Unrestricted finite colourings and used palettes
- If | A| > k| B| then every f : A → B has a fibre with more than k elements, and for nonempty B some fibre has at least ⌈ | A| / | B|⌉ elements
- Division with remainder for any nonzero divisor: for a ∈ ℤ and b ≠ 0 there are unique q, r ∈ ℤ with a = qb + r and 0 ≤ r < |b|
- A finite set with n elements has exactly C(n, 2) two-element subsets, and 2C(n, 2) = n(n-1)
- On ℕ the order is membership: m < n ⟺ m ∈ n
- For relations R and S and a set A, the collections { (b,a) : (a,b) ∈ R }, { (a,c) : ∃ b ((a,b) ∈ R ∧ (b,c) ∈ S) } and { (a,b) ∈ R : a ∈ A } are sets
- Set partitions and blocks
- 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
- The complete connection of two disjoint graphs
- G[W]=Ḡ[W] for every vertex set W
- Empty and complete graphs, complete bipartite graphs, and the convention that Pₙ and Cₙ have n vertices
- Order on the natural numbers
- Addition is cancellative
- Addition is commutative
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
Ordinary embeddings as injections preserving edges
Definition
Tagged graph families with anticomplete parts
Lemma
Independence is monotone under induced embeddings
Lemma
Clique and independence duality under complementation
Lemma
Recursion for deterministic finite graph updates
Lemma
Finite colour-class capacity and prescribed partitions
Lemma
Rigidity of mutual ordinary embeddings
Lemma
Transport, restriction and relabelling of finite colourings
Lemma
Connected subgraphs cannot cross anticomplete parts
Lemma
Independence numbers of disjoint families and complete joins
Lemma
Complementation transports induced copies on fixed vertices
Lemma