Alphabeta MathPersonal research
Article items · 03 — Order, size, complement and independence number
Presents 28 items from the article and its immediate prerequisites, covering dependency levels 2–5.
1 · Prerequisites
- Graph and colouring conventions
- The cardinality | A| of a finite set
- Cliques, independent sets, clique number and independence number
- Graph isomorphisms, automorphisms and graph complements
- A finite set with n elements has exactly C(n, 2) two-element subsets, and 2C(n, 2) = n(n-1)
- A subset of a finite set is finite, with | B| ≤ | A|, and equality holds if and only if B = A
- r-uniform hypergraphs and complete balanced r-partite r-graphs K⁽ʳ⁾_s,…,s
- Berge cycles, incidence graphs and girth
- Weak hypergraph colourings with singleton boundary
- Induced embeddings and induced copies of a graph
- Unrestricted finite colourings and used palettes
- Ordinary embeddings as injections preserving 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
- Walks, closed walks, trails, paths and cycles, with length equal to the number of traversed edges
- Connected subgraphs cannot cross anticomplete parts
- Block containment and monotonicity under subgraphs
- Cutvertices, 2-connected pieces and nontrivial blocks
- Vertex and edge deletion, edge contraction, graph minors, subdivisions and topological minors
- A bridge as an edge whose deletion increases the number of connected components
- Neighbourhood attachments indexed by induced embeddings
- 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
- 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
- The well-ordering principle
- The disjoint multiple qA
- Finite colour-class capacity and prescribed partitions
- Empty and complete graphs, complete bipartite graphs, and the convention that Pₙ and Cₙ have n vertices
- Walks, paths, connectedness and components in a simple graph on an arbitrary vertex set
- Berge girth at least three forces linearity
- Rigidity of mutual ordinary embeddings
- Join of graphs
- Completing a restricted target with universal clique vertices
- 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
- Order on the natural numbers
- Addition is cancellative
- Addition is commutative
- Edge-Ramsey class terminology in the motivation
- Jacob Fox, Andrey Grinshpun, Anita Liebenau, Yury Person, and Tibor Szabó, What is Ramsey-equivalent to a clique? · PDF p. 1, Abstract; p. 2, Introduction (definitions); p. 3, Conventions and Notation; p. 12, Section 4, Question 4.3
- Complementation transports induced copies on fixed vertices
- Transport, restriction and relabelling of finite colourings
- Finite maximal extension of a 2-connected subgraph
- Every edge belongs to exactly one nontrivial block
- A bipartite graph and a proper two-colouring of its vertices
- Reinhard Diestel, Graph Theory, sixth edition, Chapter 3 · Section 3.1, printed p. 64 block definition/overlap paragraph; p. 65 block graph definition; p. 66 Lemma 3.1.4
- Finite edge-union sparsity excludes short Berge cycles
- Finite sparse uniform hypergraphs obstruct a prescribed palette
- The finite graph boundary gives two-uniform witnesses
- A nonempty simple graph is a tree if and only if each pair of vertices is joined by exactly one path
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
DefinitionDependency level 2
Order, size, complement and independence number
DefinitionDependency level 2
Hypergraph terminology used in Construction 1
DefinitionDependency level 2
Induced forbidden-subgraph class
DefinitionDependency level 2
Induced vertex-Ramsey class
DefinitionDependency level 2
Ordinary vertex-Ramsey class
LemmaDependency level 2
Avoidance using separated palettes and anticomplete attachments
LemmaDependency level 2
Block-hitting deletion lowers maximum block order
LemmaDependency level 2
One representative from each matching attachment reconstructs the target
LemmaDependency level 2
Small 2-connected subgraphs localise in high-girth pieces
DefinitionDependency level 3
Blocks and the parameter beta
DefinitionDependency level 3
Ramsey repetition property at fixed k
ExampleDependency level 3
Complete-graph separator when orders differ
ExampleDependency level 3
Single-vertex target case
LemmaDependency level 3
Hyperedge intersection consequence in Construction 1
LemmaDependency level 3
Orienting equal-order non-isomorphic targets
LemmaDependency level 3
Completion inside the join separator
Open problemDependency level 3
Connected non-isomorphic graphs and edge-Ramsey classes
PropositionDependency level 3
Complementation preserves distinction of induced classes
PropositionDependency level 3
The k=1 case
ExampleDependency level 4
Join separator for equal-order targets
LemmaDependency level 4
Connected targets have repetition
LemmaDependency level 4
Ordering targets and excluding H1 from H2
TheoremDependency level 4
Block incidence tree and containment contract
TheoremDependency level 4
Finite high-girth hypergraphs with no weak k-colouring
DefinitionDependency level 5
Block-cutvertex tree terminology
LemmaDependency level 5
The implicit r=1 base case
LemmaDependency level 5
Rooted block exposure and attachment separation
TheoremDependency level 5