Alphabeta MathPersonal research
Article items · 04 — High-girth hypergraphs for Construction 1
Presents 29 items from the article and its immediate prerequisites, covering dependency levels 5–19.
1 · Prerequisites
- A finite simple graph is a finite vertex set together with a set of two-element vertex subsets
- Hypergraph terminology used in Construction 1
- Finite high-girth hypergraphs with no weak k-colouring
- Block-cutvertex tree terminology
- Connected graphs and connected components defined by the existence of vertex paths
- Subgraphs, induced subgraphs and spanning subgraphs
- Graph and colouring conventions
- Graph realisations with possibly different hyperedge pieces
- Injection, surjection, bijection
- The cardinality | A| of a finite set
- Berge cycles, incidence graphs and girth
- Induced embeddings and induced copies of a graph
- Berge girth at least three forces linearity
- Linear realisations preserve induced pieces
- Order, size, complement and independence number
- Rooted block exposure and attachment separation
- The principle of mathematical induction
- Blocks and the parameter beta
- Cutvertices, 2-connected pieces and nontrivial blocks
- Block-hitting deletion lowers maximum block order
- Nonempty remainder after deleting an independent set
- Vertex and edge deletion, edge contraction, graph minors, subdivisions and topological minors
- Induced vertex-Ramsey class
- Unrestricted finite colourings and used palettes
- Weak hypergraph colourings with singleton boundary
- Ordering targets and excluding H1 from H2
- Cliques, independent sets, clique number and independence number
- Walks, closed walks, trails, paths and cycles, with length equal to the number of traversed edges
- Small 2-connected subgraphs localise in high-girth pieces
- Clique and independence duality under complementation
- Complementation transports induced copies on fixed vertices
- The complete graph on an n-element vertex set has C(n, 2) edges
- The set [A]ᵏ of k-element subsets and the binomial coefficient C(n, k) := | [n]ᵏ|
- Induced forbidden-subgraph class
- Finite colour-class capacity and prescribed partitions
- Empty and complete graphs, complete bipartite graphs, and the convention that Pₙ and Cₙ have n vertices
- Join of graphs
- Tagged graph families with anticomplete parts
- The connected components of a graph partition its vertex set and are its maximal connected subgraphs
- Independence numbers of disjoint families and complete joins
- Independence is monotone under induced embeddings
- Block containment and monotonicity under subgraphs
- The disjoint multiple qA
- Transport, restriction and relabelling of finite colourings
- Ordinary embeddings as injections preserving edges
- Ramsey repetition property at fixed k
- Connected targets have repetition
- Graph isomorphisms, automorphisms and graph complements
- Neighbourhood attachments indexed by induced embeddings
- Recursion for deterministic finite graph updates
- The natural numbers ℕ (von Neumann)
- Order on the natural numbers
- ≤ is a linear order on ℕ
- The well-ordering principle
- A subset of a finite set is finite, with | B| ≤ | A|, and equality holds if and only if B = A
- Complementation preserves distinction of induced classes
- Complement of a disconnected graph is connected
- On ℕ the order is membership: m < n ⟺ m ∈ n
- One representative from each matching attachment reconstructs the target
- Avoidance using separated palettes and anticomplete attachments
- The implicit r=1 base case
- The k=1 case
- Single-vertex target case
- Ordinary vertex-Ramsey class
- Ordinary part of Theorem 1.1
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
TheoremDependency level 5
High-girth hypergraphs for Construction 1
AlgorithmDependency level 6
Greedy choice in the block-cutvertex tree
DefinitionDependency level 6
Construction 1: graph G(H,q,k)
LemmaDependency level 7
Copies on hyperedges are induced
LemmaDependency level 7
The greedy set is independent and meets every block
LemmaDependency level 8
Independent deletion decreases beta
PropositionDependency level 8
Construction 1 gives an induced vertex-Ramsey graph
DefinitionDependency level 9
The independent set I and remainder F
PropositionDependency level 9
Induced Ramsey graph with the same independence number
TheoremDependency level 9
Nonemptiness attributed to Folkman
ExampleDependency level 10
Edgeless choice of A
LemmaDependency level 10
Independence gap for the join of components
LemmaDependency level 10
Block bounds in the edged-F case
LemmaDependency level 11
Disjoint-copy witness against repetition
LemmaDependency level 11
Block exclusion in the high-girth base graph
LemmaDependency level 12
Lemma 2.1: repetition characterizes connectivity
PropositionDependency level 12
Existence of the base graph A
DefinitionDependency level 13
Recursive graphs Ar and their attachments
LemmaDependency level 13
Reduction to connected targets
LemmaDependency level 13
Fewer colours for the base graph
LemmaDependency level 14
A monochromatic F extends through all-colour attachments
LemmaDependency level 14
Inductive colouring avoiding H1
LemmaDependency level 14
An attachment using fewer colours supplies H2
LemmaDependency level 15
Inductive Ramsey membership for H2
RemarkDependency level 15
Figure 1: recursive construction and red witness
PropositionDependency level 16
Invariant of the recursive induced separator
ExampleDependency level 17
Final induced-Ramsey separator
TheoremDependency level 18
Induced part of Theorem 1.1
TheoremDependency level 19