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
- Cutvertices, 2-connected pieces and nontrivial blocks
- Walks, closed walks, trails, paths and cycles, with length equal to the number of traversed edges
- A finite simple graph is a finite vertex set together with a set of two-element vertex subsets
- Subgraphs, induced subgraphs and spanning subgraphs
- Connected graphs and connected components defined by the existence of vertex paths
- The union ⋃ x of a set, and the binary union a ∪ b := ⋃ {a,b}
- ⋃ ∅ = ∅, ⋃ {a} = a, ⋃ {a,b} = a ∪ b, ⋂ {a} = a, and ⋂ {a,b} = a ∩ b
- A subset of a finite set is finite, with | B| ≤ | A|, and equality holds if and only if B = A
- Every walk between two vertices contains a path between the same endpoints
- Vertex and edge deletion, edge contraction, graph minors, subdivisions and topological minors
- Berge cycles, incidence graphs and girth
- r-uniform hypergraphs and complete balanced r-partite r-graphs K⁽ʳ⁾_s,…,s
- The cardinality | A| of a finite set
- Double counting: ∑_x ∈ X| Rₓ| = | R| = ∑_y ∈ Y| Rʸ| for a relation between finite sets
- The sum ∑_i ∈ S aᵢ over a finite index set, and its product form
- Laws of finite sums and products in ℕ, and ι(∑_k<n aₖ) = ∑_k<n ι(aₖ)
- Graph realisations with possibly different hyperedge pieces
- Small edge supports in a high-girth hypergraph
- Two-connected subgraphs stay in one incidence-forest piece
- Cycles, trees and forests in a simple graph on an arbitrary vertex set
- Graph isomorphisms, automorphisms and graph complements
- The well-ordering principle
- Injection, surjection, bijection
- Block containment and monotonicity under subgraphs
- A bridge as an edge whose deletion increases the number of connected components
- Cliques, independent sets, clique number and independence number
- Weak hypergraph colourings with singleton boundary
- 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
- The reals form a totally ordered field
- Laws of finite sums and finite products
- Proper vertex colourings and chromatic number
- P. Erdős, Graph theory and probability, Canadian Journal of Mathematics 11 (1959), 34–38 · Printed p.35 (PDF p.2), paragraph following equation (5), beginning “Now (4) clearly shows”; p.36, paragraph displaying a given closed circuit and counting its distinct ordered vertices; definition of h(k,l) and equation (4) on p.34; proof of (4), pp.35–37
- Real powers for positive bases, with the zero-base positive-exponent convention
- The exponent, product, quotient, and iterated-power laws for positive real bases and real exponents
- The natural logarithm as the inverse of the exponential function
- Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm
- The exponential function is strictly increasing
- The exponential is positive and satisfies exp(-x)=1/exp(x)
- The Cauchy-sequence reals are Archimedean
- P. Erdős and A. Hajnal, On chromatic number of graphs and set-systems, Acta Mathematica Academiae Scientiarum Hungaricae 17 (1966), 61–99 · §13, Definition 13.2, printed p.94 (PDF p.34), and Theorem 13.3, printed p.95 (PDF p.35)
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
Lemma
Cycles are 2-connected
Lemma
Union closure for overlapping 2-connected subgraphs
Lemma
Finite maximal extension of a 2-connected subgraph
Lemma
A Berge cycle bounds the union of its hyperedges
Lemma
Small 2-connected subgraphs localise in high-girth pieces
Lemma
Block-hitting deletion lowers maximum block order
Lemma
Nonbridge edges lie on 2-connected cycles
Lemma
Finite edge-union sparsity excludes short Berge cycles
Lemma
Small independent sets obstruct weak colourings
Lemma
The finite graph boundary gives two-uniform witnesses
Lemma
Every edge belongs to exactly one nontrivial block
Lemma
Finite sparse uniform hypergraphs obstruct a prescribed palette
Theorem