2021/03/16 by Goaoc, Xavier, Holmsen, Andreas F., Patáková, Zuzana
#Combinatorics (math.CO) #Computational Geometry (cs.CG) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2103.09286
In this paper we study generalizations of classical results on intersection patterns of set systems in ℝd, such as the fractional Helly theorem or the (p,q)-theorem, in the setting of arbitrary triangulable spaces with a forbidden homological minor. Given a simplicial complex K and an integer b, we say that a family F of subcomplexes of some simplicial complex U is a (K,b)-free cover if (i) K is a forbidden homological minor of U, and (ii) the jth reduced Betti number βj(\bigcap_S∈ GS,ℤ2) is strictly less than b for all 0≤ j < dim K and all nonempty subfamilies G⊆ F. We show that for every K and b, the fractional Helly number of a (K,b)-free cover is at most μ(K)+1, where μ(K) is the maximum sum of the dimensions of two disjoint faces in~K. This implies that the assertion of the (p,q)-theorem holds for every p ≥ q > μ(K) and every (K,b)-free cover F. For b=1 and a suitable K this recovers the original (p,q)-theorem and its generalization to good covers. Interestingly, our results show that that the range of parameters (p,q) for which the (p,q)-theorem holds is independent of b. Our proofs use Ramsey-type arguments combined with the notion of stair convexity of Bukh et al. to construct (forbidden) homological minors in cubical complexes.