Xavier Goaoc

Xavier Goaoc, Andreas F. Holmsen, Zuzana Patáková

In this paper we study generalizations of classical results on intersection patterns of set systems in $\mathbb{R}^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 $\mathcal{F}$ of subcomplexes of some simplicial complex $X$ is a $(K,b)$-free cover if (i) $K$ is a forbidden homological minor of $X$, and (ii) the $j$th reduced Betti number $\tildeβ_j(\bigcap_{S\in {\mathcal{G}}}S,\mathbb{Z}_2)$ is strictly less than $b$ for all $0\leq j < \dim K$ and all nonempty subfamilies $\mathcal{G}\subseteq \mathcal{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 \ge q > μ(K)$ and every $(K,b)$-free cover $\mathcal{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 certain cubical complexes.

Sergey Avvakumov, Marguerite Bin, Xavier Goaoc

A theorem of Matoušek asserts that for any $k \ge 2$, any set system whose shatter function is $o(n^k)$ enjoys a fractional Helly theorem of order $k$: in the $k$-wise intersection hypergraph, positive density implies a linear-size clique. Kalai and Meshulam conjectured a generalization of that phenomenon to homological shatter functions. It was verified for set systems with bounded homological shatter functions and ground set with a forbidden homological minor (which includes $\mathbb{R}^d$ by a homological analogue of the van Kampen-Flores theorem). We present two contributions to this line of research: - We study homological minors in certain manifolds (possibly with boundary), for which we prove analogues of the van Kampen-Flores theorem and of the Hanani-Tutte theorem. - We introduce graded analogues of the Radon and Helly numbers of set systems and relate their growth rate to the original parameters. This allows to extend the verification of the Kalai-Meshulam conjecture for sufficiently slowly growing homological shatter functions.

Mathilde Bouvel, Valentin Féray, Xavier Goaoc et al.

Chirotopes are a common combinatorial abstraction of (planar) point sets. In this paper we investigate decomposition methods for chirotopes, and their application to the problem of counting the number of triangulations supported by a given planar point set. In particular, we generalize the convex and concave sums operations defined by Rutschmann and Wettstein for a particular family of chirotopes (which they call chains), and obtain a precise asymptotic estimate for the number of triangulations of the double circle, using a functional equation and the kernel method.

Boris Bukh, Xavier Goaoc, Alfredo Hubard et al.

We consider incidences among colored sets of lines in $\mathbb{R}^d$ and examine whether the existence of certain concurrences between lines of $k$ colors force the existence of at least one concurrence between lines of $k+1$ colors. This question is relevant for problems in 3D reconstruction in computer vision.