Berge cycles, incidence graphs and girth

A finite hypergraph is a pair $\mathcal{H}=(V,\mathcal{E})$ where $V$ is a finite set and $\mathcal{E}$ is a set of subsets of $V$; its members are hyperedges. Its incidence graph is the finite simple graph whose vertex set is $(V\times \{0\})\cup (\mathcal{E}\times \{1\})$ and whose edges are exactly the pairs $\{(v,0),(e,1)\}$ for which $v\in e$. Its two displayed vertex sets are the parts of the graph: every graph edge joins one part to the other.

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}$ such that $x_i\in e_i\cap e_{i+1}$ for every $i$, with indices modulo $s$. The Berge girth is the least length of a Berge cycle, or $\mathrm{\infty }$ if no Berge cycle exists; $\mathrm{\infty }$ is greater than every integer. The hypergraph is linear if any two distinct hyperedges have at most one common vertex.

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

A finite simple graph is a finite vertex set together with a set of two-element vertex subsets

The Cartesian product A × B := { z ∈ P(P(A ∪ B)) : ∃ a ∈ A ∃ b ∈ B z = (a,b) }

The tags $0$ and $1$ distinguish the two kinds of node even when a vertex is itself a hyperedge. The two parts and the incidence-edge set are finite; each incidence edge has two distinct endpoints and is an unordered pair, so this construction is a finite simple graph. An $r$-uniform hypergraph in the cited definition is a special case of the finite hypergraphs defined here. The possible cycle lengths lie between $2$ and both $\mathrm{\mid }V\mathrm{\mid }$ and $\mathrm{\mid }\mathcal{E}\mathrm{\mid }$, so a nonempty set of possible lengths has a least element; the separate $\mathrm{\infty }$ convention covers the empty case. Linearity is a definite condition on pairs of hyperedges.