Quantitative Helly-type theorems via hypergraph chains
Let \(V\) be a possibly infinite set. The infinite sequence \((\mathcal{H}_\ell)_{\ell\in \mathbb{Z}}\) of hypergraphs over the base set \(V\) is said to be a hypergraph chain if every \(\mathcal{H}_\ell\) is downwards closed and for all \(\ell \in \mathbb{Z}\), \(\mathcal{H}_\ell \subset\mathcal{H}_{\ell+1}\). A hypergraph chain \((\mathcal{H}_\ell)_{\ell\in\mathbb{Z}}\) over a base set \(V\) is said to have Helly number \(h\) if, for every \(S\subseteq V\), \(\binom{S}{h} \subset \mathcal{H}_\ell\) implies \(S\in\mathcal{H}_{\ell+1}\). Also, a hypergraph chain \((\mathcal{H}_\ell)_{\ell\in\mathbb{Z}}\) over a base set \(V\) is said to have colourful Helly number \(k\) if, whenever \(S_1,\ldots,S_k\) are finite subsets (colour classes) of \(V\), and \(S_1\otimes\dots \otimes S_k \subset\mathcal{H}_\ell\), then there is a colour class \(S_j\) with \(S_j \in\mathcal{H}_{\ell+1}\). Lastly, a hypergraph chain \((\mathcal{H}_\ell)_{\ell\in\mathbb{Z}}\) over a base set \(V\) is said to have fractional Helly number \(k\) if there exists a function \(\beta: (0,1) \to (0,1)\) such that, for every finite set \(S\subset V\), if \(|\mathcal{H}_\ell \cap \binom{S}{k}| \geq \alpha\binom{|S|}{k}\), with some \(\alpha\in(0,1)\), then there exists an \(S^\prime \subset S\) with \(|S^\prime |\geq \beta (\alpha)|S|\) and \(S^\prime \in\mathcal{H}_{\ell+1}\).\N\NThe main theorem of this paper says that if the hypergraph chain \((\mathcal{H}_\ell)_\ell\in{\mathbb Z}\) has colourful Helly number \(k\), then the hypergraph chain \((\mathcal{H}_{(k+1)\ell})_\ell\in{\mathbb Z}\) has fractional Helly number \(k\).\N\NThe author also discusses the problem of whether the fractional Helly number can go below the colourful Helly number.
scientific article; zbMATH DE number 7882977
scientific article