Construction 1: graph G(H,q,k)

PDF p. 1: Construction 1; PDF p. 2: Construction 1, definition of G

Let $H=(V(H),E(H))$ be a finite simple graph with at least one vertex, let $q\ge 3$ and $k\ge 1$ be integers, and put $r=\mathrm{\mid }V(H)\mathrm{\mid }$. Choose a finite $r$-uniform hypergraph $\mathcal{H}=(V,\mathcal{E})$ of Berge girth at least $q$ with no weak $k$-colouring. Here each hyperedge is an $r$-element subset of $V$; Berge girth is the least length of a Berge cycle, or infinity if there is none; and a weak $k$-colouring assigns one of $k$ colours to each vertex so that every hyperedge has two differently coloured vertices.

For each $e\in \mathcal{E}$, choose a bijection $f_e:V(H)\to e$ and define $E_e=\{\{f_e(x),f_e(y)\}:\{x,y\}\in E(H)\}$. The constructed graph is $G=(V,{\bigcup }_{e\in \mathcal{E}}{E}_e)$. Its piece on $e$ is the graph $(e,E_e)$, a copy of $H$ under $f_e$. We write $G(H,q,k)$ for a graph obtained by these choices; the notation does not specify a unique graph without the choices of $\mathcal{H}$ and the bijections.

Graph and colouring conventions

Hypergraph terminology used in Construction 1

High-girth hypergraphs for Construction 1

Graph realisations with possibly different hyperedge pieces

Injection, surjection, bijection

The cardinality | A| of a finite set

The high-girth hypergraph theorem supplies a finite hypergraph with the stated properties for every allowed $r,q,k$. For $r\ge 2$ its weak chromatic number is defined and at least $k+1$; for $r=1$ the theorem supplies a singleton-edge witness with no weak colouring, whose weak chromatic number is undefined under the adopted convention. Thus the no-weak-colouring condition states the property needed in both cases.

Each hyperedge $e$ and $V(H)$ have the same finite cardinality, so a bijection $f_e$ exists; the finite family of hyperedges permits these choices together. Injectivity makes the image of every edge of $H$ a two-element subset of $e$. The hyperedge-indexed realisation therefore defines a finite simple graph on $V$, and its specified transported piece is isomorphic to $H$ via $f_e$. Once the choices are fixed, the displayed edge-set formula determines $G$ uniquely.

The article describes the pieces as induced copies. That further assertion is treated separately; the definition above only places the edge sets and does not assume that other pieces add no edges inside a hyperedge.