Extremal bi-Helly families
type: Item
instance of: scholarly article
title: Extremal bi-Helly families
zbMATH Open document ID: 0943.05057
DOI: 10.1016/S0012-365X(99)00192-2
author: Zsolt Tuza
published in: Discrete Mathematics
publication date: 2000-08-28T00:00:00Z
review text: \textit{V. I. Voloshin} [Australas. J. Comb. 11, 25-45 (1995; Zbl 0827.05027)] introduced the concept of \((p,q,s)\)-Helly hypergraph. A hypergraph is \(p\)-wise \(q\)-intersecting if the intersection of every \(p\) or fewer edges contains at least \(q\) vertices. A hypergraph \(\mathcal{H}\) is said to be \((p,q,s)\)-Helly (\(p\geq 2\) and \(q,s \geq 1\)) if \(|\bigcap_{H\in {\mathcal{H}}^\prime} H|\geq s\) holds for every \(p\)-wise \(q\)-intersecting subhypergraph \({\mathcal{H}}^\prime \subseteq \mathcal{H}\). The case \(p=2\) and \(q=s\) is studied in the paper. The main result states that the maximal number of \(r\)-tuples (edges) in a \(r\)-uniform \((2, k, k)\)-Helly family on \(n\) vertices is equal to \(\binom{n-k}{r-k}\) for all \(n\geq r >2k \geq 4\). For \(r=3,4\) some interesting asymptotic bounds are presented.
reviewed by: Fedor V. Fomin
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 1420395
zbMATH Keywords: hypergraph
zbMATH Keywords: Helly property
zbMATH Keywords: pairwise \(k\)-intersecting
zbMATH Keywords: extremal problem
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1420395