On Helly Hypergraphs with Variable Intersection Sizes

Abstract

A hypergraph \(\mathcal{H}\) is said to be \(p\)-Helly when every \(p\)-wise intersecting partial hypergraph \(\mathcal{H}’\) of \(H\) has nonempty total intersection. Such hypergraphs were characterized by Berge and Duchet in 1975, and since then they have appeared in various contexts, particularly for \(p=2\), where they are known as Helly hypergraphs. An interesting generalization due to Voloshin considers both the number of intersecting sets and their intersection sizes: a hypergraph \(\mathcal{H}\) is \((p,q,s)\)-Helly if every \(p\)-wise \(q\)-intersecting partial hypergraph \(\mathcal{H}’\) of \(H\) has total intersection of cardinality at least \(s\). This work proposes a characterization for \((p,q,s)\)-Helly hypergraphs, leading to an efficient algorithm for recognizing such hypergraphs when \(p\) and \(q\) are fixed parameters.