Quantitative Helly-type theorems via hypergraph chains
type: Item
instance of: scholarly article
title: Quantitative Helly-type theorems via hypergraph chains
DOI: 10.37236/11989
author: Attila Jung
published in: The Electronic Journal of Combinatorics
publication date: 2024-07-18T00:00:00Z
review text: 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.
reviewed by: Josef Lauri
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 52A35
Mathematics Subject Classification ID: 52A38
zbMATH DE Number: 7882977
zbMATH Keywords: hypergraph chains
zbMATH Keywords: Helly numbers
MaRDI profile type: Publication
cites work: Transversal numbers for hypergraphs arising in geometry
cites work: A generalization of Caratheodory's theorem
cites work: Quantitative Helly-Type Theorems
cites work: BRASCAMP–LIEB INEQUALITY AND QUANTITATIVE VERSIONS OF HELLY'S THEOREM
cites work: Colorful Helly-type theorems for the volume of intersections of convex bodies
cites work: The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
cites work: Quantitative combinatorial geometry for continuous parameters
cites work: Q4400994
cites work: Large cliques in hypergraphs with forbidden substructures
cites work: Quantitative fractional Helly and \((p,q)\)-theorems
cites work: A Problem of Geometry in R n
cites work: Q4530626
cites work: Proof of a conjecture of Bárány, Katchalski and Pach
cites work: Quantitative \((p, q)\) theorems in combinatorial geometry
cites work: Quantitative combinatorial geometry for concave functions
description: scientific article; zbMATH DE number 7882977