Alphabeta MathPersonal research
Hypergraph girth and graph blocks
Connect Berge girth and incidence forests with block decomposition and vertex deletion, supplying induced graph realisations, forbidden-block control and the induction remainder.
1 · Prerequisites
- The Axiom of Union: ∀ x ∃ y ∀ z (z ∈ y ↔ ∃ s (s ∈ x ∧ z ∈ s))
- The Axiom of Extensionality: ∀ x ∀ y (∀ z (z ∈ x ↔ z ∈ y) → x = y)
- The unordered pair {x,y} and the singleton {x} = {x,x}
- If a ∈ A and b ∈ B then (a,b) ∈ P(P(A ∪ B))
- The Axiom Schema of Separation: for each formula φ, ∀ p̄ ∀ x ∃ y ∀ z (z ∈ y ↔ (z ∈ x ∧ φ(z,p̄)))
- The Kuratowski ordered pair (a,b) := {{a},{a,b}}
- The power set P(x) = { z : z ⊆ x }
- 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
- The image R[A] and the preimage R⁻¹[B] of a set under a relation
- Finite, countably infinite, countable, uncountable
- The pigeonhole principle on ℕ
- Equinumerous sets, A ≈ B and A ⪯ B
- The natural numbers ℕ (von Neumann)
- On ℕ the order is membership: m < n ⟺ m ∈ n
- Order on the natural numbers
- Unless stated otherwise, graph means finite, simple and undirected; orders, sizes and empty-set conventions are fixed here
- Walks, closed walks, trails, paths and cycles, with length equal to the number of traversed edges
- Every walk between two vertices contains a path between the same endpoints
- lvertP(A)| = 2^| A| for finite A
- A subset of a finite set is finite, with | B| ≤ | A|, and equality holds if and only if B = A
- The principle of mathematical induction
- The set [A]ᵏ of k-element subsets and the binomial coefficient C(n, k) := | [n]ᵏ|
- Empty and complete graphs, complete bipartite graphs, and the convention that Pₙ and Cₙ have n vertices
- Simple graphs on an arbitrary vertex set
- Walks, paths, connectedness and components in a simple graph on an arbitrary vertex set
- The connected components of a graph partition its vertex set and are its maximal connected subgraphs
- Every walk contains a path between the same endpoints, of no greater length
- Graph isomorphisms, automorphisms and graph complements
- Induced embeddings and induced copies of a graph
- Maria Axenovich and Annette Karrer, High girth hypergraphs with unavoidable monochromatic or rainbow edges, arXiv:1607.06600v2 · Section 1, cycle and girth paragraph immediately before Theorem 1
- An indexed family (Aᵢ)_i ∈ I is a function with domain I; {Aᵢ : i ∈ I} is its range
- ⋃_i ∈ I Aᵢ := ⋃ {Aᵢ : i ∈ I}, and ⋂_i ∈ I Aᵢ := ⋂ {Aᵢ : i ∈ I} for I ≠ ∅
- The product rule: | A × B| = | A| | B|, and |∏_i<m Aᵢ| = ∏_i<m| Aᵢ|
- ≤ is a linear order on ℕ
- The well-ordering principle
- The von Neumann naturals form a Peano system
- Every nonzero natural number is a successor
- Discreteness: σ(n) is the immediate successor
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
The union ⋃ x of a set, and the binary union a ∪ b := ⋃ {a,b}
Definition
The Cartesian product A × B := { z ∈ P(P(A ∪ B)) : ∃ a ∈ A ∃ b ∈ B z = (a,b) }
Definition
Injection, surjection, bijection
Definition
The cardinality | A| of a finite set
Definition
A finite simple graph is a finite vertex set together with a set of two-element vertex subsets
Definition
Subgraphs, induced subgraphs and spanning subgraphs
Definition
Connected graphs and connected components defined by the existence of vertex paths
Definition
Cliques, independent sets, clique number and independence number
Definition
r-uniform hypergraphs and complete balanced r-partite r-graphs K⁽ʳ⁾_s,…,s
Definition
Cycles, trees and forests in a simple graph on an arbitrary vertex set
Definition
Vertex and edge deletion, edge contraction, graph minors, subdivisions and topological minors
Definition
A bridge as an edge whose deletion increases the number of connected components
Theorem
A nonempty simple graph is a tree if and only if each pair of vertices is joined by exactly one path
Definition
Unrestricted finite colourings and used palettes
Definition
Ordinary embeddings as injections preserving edges
Definition
Berge cycles, incidence graphs and girth
Definition
Graph realisations with possibly different hyperedge pieces
Definition
Cutvertices, 2-connected pieces and nontrivial blocks
Definition
Weak hypergraph colourings with singleton boundary
Lemma
Linear realisations preserve induced pieces
Lemma
Berge girth at least three forces linearity
Lemma
Small edge supports in a high-girth hypergraph
Lemma
Two-connected subgraphs stay in one incidence-forest piece
Lemma
Block containment and monotonicity under subgraphs
Lemma