Hypergraph terminology used in Construction 1

PDF p. 1: Construction 1; PDF p. 2: Construction 1, continuation

Let $H$ be a finite simple graph with at least one vertex, and write $r=\mathrm{\mid }V(H)\mathrm{\mid }$. An $r$-uniform hypergraph $\mathcal{H}=(V,\mathcal{E})$ consists of a finite vertex set $V$ and a set $\mathcal{E}$ of $r$-element subsets of $V$, called hyperedges.

For a positive integer $k$, a weak $k$-colouring of $\mathcal{H}$ is a function $c:V\to \{1,\dots ,k\}$ for which every hyperedge contains two vertices assigned different colours. Its weak chromatic number ${\chi }_w(\mathcal{H})$ is the least positive $k$ for which such a colouring exists, if one exists; otherwise it is undefined. Thus ${\chi }_w(\mathcal{H})\ge k+1$ includes the requirement that this number be defined. In particular, a singleton hyperedge prevents every weak colouring; if $r\ge 2$, a finite $r$-uniform hypergraph has a defined weak chromatic number.

For this treatment, a Berge cycle of length $s\ge 2$ consists of distinct hyperedges $e_0,\dots ,e_{s-1}$ and distinct vertices $x_0,\dots ,x_{s-1}$ with $x_i\in e_i\cap e_{i+1}$, indices taken modulo $s$. The Berge girth is the least such length, or $\mathrm{\infty }$ if there is no Berge cycle, with $\mathrm{\infty }$ larger than every integer. The construction's girth requirement is interpreted as Berge girth at least an integer $q\ge 3$.

Graph and colouring conventions

r-uniform hypergraphs and complete balanced r-partite r-graphs K⁽ʳ⁾_s,…,s

Weak hypergraph colourings with singleton boundary

Berge cycles, incidence graphs and girth

The graph convention makes $r$ a positive integer, and the uniform-hypergraph definition specifies the finite vertex set and the hyperedges. The weak-colouring supplier gives the least-colour convention and establishes both the singleton-edge obstruction and existence of the number for finite uniform hypergraphs with $r\ge 2$. The Berge-cycle supplier specifies the least-length and infinite-girth conventions. These choices make each term definite, including when there is no cycle or no weak colouring.

If two distinct hyperedges share two distinct vertices, those edges and vertices form a Berge cycle of length two. Consequently Berge girth at least $q\ge 3$ implies that distinct hyperedges meet in at most one vertex, as required in the construction.

The article uses uniformity, chromatic number and a girth lower bound, and invokes the resulting intersection property. It does not separately define hypergraph girth at the cited passage. The Berge convention above is an explicit choice for this treatment; it is not attributed to an explicit definition in the article. This item does not assert the existence of a hypergraph satisfying the construction's parameters.