Intersection Patterns of Set Systems on Manifolds with Slowly Growing Homological Shatter Functions

Before we state our results precisely (in Section 1.2) let us provide some context and motivation, as well as introduce some necessary terminology.

Our main contribution is to confirm Conjecture 1 for some diverging homological shatter functions and on some manifolds. This decomposes into five independent results.

Throughout the paper, we work with compact piecewise-linear (PL) manifolds (possibly with boundary); see [32, $\mathrm{\S }1$] for an introduction. We first generalize Theorem 2:

This partially answers [28, Problem 3], [13, Conjecture 1.7] and [26, Conjecture 2] and extends the previous confirmation of Conjecture 1 from set systems in ${ℝ}^d$ to set systems on manifolds. This also extends several results on set systems with bounded topological complexity (Helly’s theorem, Radon’s theorem, $(p,q)$-theorem, …) from ${ℝ}^d$ to sufficiently connected manifolds (see [28, 13]). We can relax the connectivity assumption (see [2, App. B]) but not remove it.

One ingredient in the proof of Theorem 3 is the following analogue of the Hanani-Tutte theorem for homological almost-embeddings, which is of independent interest.

We formalize what we mean by general position in Section 2.

The homological shatter function ${\mathrm{\Phi }}_{ℱ}^{(h)}$ defined in Equation (1) can be reformulated as a graded version of the topological complexity ${\mathrm{hc}}_{ℱ}^{(h)}$ defined in Equation (2), where the value for parameter $t$ considers only intersections of subfamilies of size at most $t$: ${\varphi }_{ℱ}^{(h)}(t)={sup}_{\begin{array}{c}{ℱ}^{\prime }\subset ℱ\\ |{ℱ}^{\prime }|\le t\end{array}}{\mathrm{hc}}_{{ℱ}^{\prime }}^{(h)}$. We systematize this viewpoint and define graded analogues of other parameters of set systems. For instance here are the graded Radon and graded Helly numbers:

It is straightforward to see that if the graded Helly numbers of a set system do not grow fast enough, then they are ultimately stationary and the set system has bounded Helly number (Lemma 10). We prove a similar condition for (graded) Radon numbers:

As a application, we extend Patáková’s theorem from bounded to sufficiently slowly diverging homological shatter function (Corollary 12). This, in turns yields fractional Helly theorems for sufficiently slowly diverging homological shatter functions.

We then investigate more graded numbers and establish more relations between graded and ungraded numbers. As an application, we extend the Holmsen-Lee bound on ${\mathrm{\Psi }}_{\mathrm{r}\to \mathrm{fh}}(\cdot )$. Let $\mathrm{\Xi }:\mathbb{N}\to \mathbb{N}$ be the function defined by $\mathrm{\Xi }(r):=r^{r^{\lceil {\log }_{2}r\rceil }+r\lceil {\log }_{2}r\rceil }$.

With Theorem 7 we can strengthen Corollary 6, as a close inspection of the proof reveals that the function $\beta$ associated to the fractional Helly number depends only on $\mathrm{\Psi }$ and $t_0$. (It also allows a slightly faster growth than Corollary 12.) We postpone this to the full version of the paper.

Let us now prove Theorem 4. Let $K$ be a simplicial complex of dimension $k>1$ and let $T$ be a triangulation of a compact PL manifold (possibly with boundary) $ℳ$ of dimension $2k$. Let $f:C_{\ast }(K;{\mathbb{Z}}_2)\to C_{\ast }(T;{\mathbb{Z}}_2)$ be a non-trivial chain map in general position such that the images of any two non-adjacent $k$-faces $\sigma ,\tau \in K$ intersect evenly.

Our goal is to prove that $K$ is a homological minor of $ℳ$. This requires repeatedly subdividing the triangulation $T$. In what follows, every time we subdivide a triangulation $T_i$ into $T_{i+1}$, all chain maps to $T_i$ and subcomplexes of $T_i$ are also subdivided to $T_{i+1}$. Also, throughout the proof we identify every pure $\mathrm{\ell }$-dimensional simplicial complex with the unique $\mathrm{\ell }$-chain with coefficients in ${\mathbb{Z}}_2$ it supports; we abuse the terminology and say that we add (pure) simplicial complexes over ${\mathbb{Z}}_2$ to mean that we add the corresponding chains.

If $f$ is a homological almost-embedding we are done. Otherwise, there exist some non-adjacent $k$-faces $\sigma ,\tau \in K$ such that $f(\sigma )\cap f(\tau )$ is non-empty. By assumption, this intersection is a set of vertices of even size, so let $x,y\in f(\sigma )\cap f(\tau )$ be two distinct such vertices. Recall that $f$ is in general position, $f(\sigma )$ and $f(\tau )$ intersect generically in $x$ and in $y$. We set out to construct a refinement $T^{\prime }$ of $T$ and a new map $f^{\prime }:C_{\ast }(K;{\mathbb{Z}}_2)\to C_{\ast }(T^{\prime };{\mathbb{Z}}_2)$ that is also in general position, differs from $f$ only on $\sigma$ and $\tau$, and satisfies $f^{\prime }(\sigma )\cap f^{\prime }(\tau )=\left(f(\sigma )\cap f(\tau )\right)\setminus \{x,y\}$ as well as $f^{\prime }(\alpha )\cap f^{\prime }(\beta )=f(\alpha )\cap f(\beta )$ for any $\alpha \in \{\sigma ,\tau \}$ and any $k$-face $\beta \in K\setminus \{\sigma ,\tau \}$. Iterating this procedure produces the announced homological almost-embedding of $K$ into a triangulation of $ℳ$.

Let $B_x$ and $B_y$ denote the closed stars of $x$ and $y$ in $T$. For $z\in \{x,y\}$ and $\alpha \in \{\sigma ,\tau \}$ let $D_{\alpha ,z}:=\mathrm{supp}(f(\alpha ))\cap B_z$. Since $f(\sigma )$ and $f(\tau )$ intersect generically in $x$ and $y$, the complexes $D_{\sigma ,x},D_{\sigma ,y},D_{\tau ,x}$ and $D_{\tau ,y}$ are $k$-dimensional balls, the $(k-1)$-spheres $\partial D_{\sigma ,x}$ and $\partial D_{\tau ,x}$ have linking number $1$ in $\partial B_x$, and similarly $\partial D_{\sigma ,y}$ and $\partial D_{\tau ,y}$ have linking number $1$ in $\partial B_y$.

We subdivide $T$ into $T_1$ so that the closed star $B_x^{\prime }$ of $x$ and $B_y^{\prime }$ of $y$ in $T_1$ are disjoint from $\partial B_x$ and $\partial B_y$, respectively. In particular, for $z\in \{x,y\}$ and $\alpha \in \{\sigma ,\tau \}$, letting $D_{\alpha ,z}^{\prime }:=\mathrm{supp}(f(\alpha ))\cap B_z^{\prime }$, the pair $(\partial D_{\alpha ,z}^{\prime },\partial B_z^{\prime })$ is homeomorphic to $({𝕊}^{k-1},{𝕊}^{2k-1})$. The genericity of $x$ and $y$ in $f(\sigma )\cap f(\tau )$ is preserved through the subdivision $T\to T_1$ so the four complexes $D_{\bullet ,\bullet }^{\prime }$ are $k$-dimensional balls and their bounding spheres have the same linking numbers in $\partial B_x^{\prime }$ and $\partial B_y^{\prime }$ as their counterparts on $\partial B_x$ and $\partial B_y$.

Up to subdividing $T_1$ into $T_2$, there exist vertices $v_x^{\prime }$ and $v_y^{\prime }$ in $\partial B_x^{\prime }$ and $\partial B_y^{\prime }$, respectively, and a path $P^{\prime }$ in the 1-skeleton of $T_2$ from $v_x^{\prime }$ to $v_y^{\prime }$ such that, letting $N(P^{\prime })$ denote the closed star of $P^{\prime }$ in $T_2$, the closed star of $N(P^{\prime })$ is disjoint from the image of $f$. The union $B^{\prime }:=B_x^{\prime }\cup N(P^{\prime })\cup B_y^{\prime }$ is a ball. Observe that in $\partial B^{\prime }$, the $(k-1)$-spheres $\partial D_{\sigma ,x}^{\prime }$ and $\partial D_{\tau ,x}^{\prime }$ retain the linking number $1$ that they have on $\partial B_x^{\prime }$. Similarly, in $\partial B^{\prime }$, the $(k-1)$-spheres $\partial D_{\sigma ,y}^{\prime }$ and $\partial D_{\tau ,y}^{\prime }$ retain the linking number $1$ that they have on $\partial B_y^{\prime }$.

Thus, up to further subdividing $T_2$ into $T_3$, there exist a path $P_{\sigma }$ in the 1-skeleton of $\partial B^{\prime }$ that connects $\partial D_{\sigma ,x}^{\prime }$ to $\partial D_{\sigma ,y}^{\prime }$ and with relative interiors disjoint from the image of $f$. (Here we use that $\partial D_{\alpha ,z}^{\prime }$ is of codimension $k\ge 2$ in $\partial B^{\prime }$.) Up to subdividing the triangulation further, we can pipe $D_{\sigma ,x}$ and $D_{\sigma ,y}$ together by a tube $F_{\sigma }$ found in a neighborhood of the path $P_{\sigma }$ [32, $\mathrm{\S }5.10$]. The tube $(F_{\sigma },F_{\sigma }\cap D_{\sigma ,x},F_{\sigma }\cap D_{\sigma ,y})$ is homeomorphic to $({𝔻}^k\times [0,1],{𝔻}^k\times \{0\},{𝔻}^k\times \{1\})$. Moreover, by the (PL) general position theorem for embeddings [32, $\mathrm{\S }$5.3], we can take $F_{\sigma }$ such that $\partial B^{\prime }$ and $\partial F_{\sigma }$ intersect in a generic way. By taking $F_{\sigma }$ in a sufficiently small neighborhood $U$ of $P_{\sigma }$ so that $(U,\partial B^{\prime }\cap U)$ is homeomorphic to $({ℝ}^{2k},{ℝ}^{2k-1}\times \left\{0\right\})$, and the triple $(F_{\sigma }\cap \partial B^{\prime },F_{\sigma }\cap D_{\sigma ,x}\cap \partial B^{\prime },F_{\sigma }\cap D_{\sigma ,y}\cap \partial B^{\prime })$ is homeomorphic to $({𝔻}^{k-1}\times [0,1],{𝔻}^{k-1}\times \{0\},{𝔻}^{k-1}\times \{1\})$.

Now, let $C_{\sigma }$ be the sum $D_{\sigma ,x}+\partial F_{\sigma }+D_{\sigma ,y}$ (over ${\mathbb{Z}}_2$). Note that $C_{\sigma }$ is contained in the union of $B_x\cup B_y$ and the closed star of $N(P^{\prime })$, and therefore intersects the image of $f$ only inside $B_x\cup B_y$. We note that $F_{\sigma }\cap \partial B^{\prime }$ also pipes the $(k-1)$-spheres $D_{\sigma ,x}\cap \partial B^{\prime }$ and $D_{\sigma ,y}\cap \partial B^{\prime }$. Indeed, $(F_{\sigma }\cap \partial B^{\prime },F_{\sigma }\cap D_{\sigma ,x}\cap \partial B^{\prime },F_{\sigma }\cap D_{\sigma ,y}\cap \partial B^{\prime })=(F_{\sigma }\cap \partial B^{\prime },F_{\sigma }\cap \partial (D_{\sigma ,x}\cap B^{\prime })$, $F_{\sigma }\cap \partial (D_{\sigma ,y}\cap B^{\prime }))$ is homeomorphic to $({𝔻}^{k-1}\times [0,1],{𝔻}^{k-1}\times \{0\},{𝔻}^{k-1}\times \{1\})$. It follows that $C_{\sigma }\cap \partial B^{\prime }$ is homeomorphic to the connected sum of two $(k-1)$-spheres, and is therefore homeomorphic to a $(k-1)$-sphere.

We claim that, in $\partial B^{\prime }$, the linking number between $C_{\sigma }\cap \partial B^{\prime }$ and $D_{\tau ,x}\cap \partial B^{\prime }$ equals the linking number between $D_{\sigma ,x}\cap \partial B^{\prime }$ and $D_{\tau ,x}\cap \partial B^{\prime }$, that is $1$. This follows from the fact that the chain $C_{\sigma }$ differs from $D_{\sigma ,x}$ by $\partial F_{\sigma }+D_{\sigma ,y}$, and that each of $\partial F_{\sigma }\cap \partial B^{\prime }$ and $D_{\sigma ,y}\cap \partial B^{\prime }$ is a boundary in $\partial B^{\prime }\setminus D_{\tau ,x}$. The same claim holds if we exchange $x$ for $y$.

Altogether, we get that $D_{\tau ,x}\cap \partial B^{\prime }$ and $D_{\tau ,y}\cap \partial B^{\prime }$ are in the same homology class in $\partial B^{\prime }\setminus C_{\sigma }$. Hence, their sum is a boundary, and there exists a chain $\eta \in C_k(\partial B^{\prime }\setminus C_{\sigma };{\mathbb{Z}}_2)$ such that the support of $\partial \eta$ is the sum over ${\mathbb{Z}}_2$ of $D_{\tau ,x}\cap \partial B^{\prime }$ and $D_{\tau ,y}\cap \partial B^{\prime }$. We finally set

We set $f^{\prime }(\omega )=f(\omega )$ for every other face $\omega \in K$. Extending $f^{\prime }$ linearly yields a chain map, since both $f^{\prime }(\sigma )-f(\sigma )$ and $f^{\prime }(\tau )-f(\tau )$ are cycles ²²2They are even boundaries, ensuring that $f^{\prime }$ is chain homotopic to $f$. The chain map $f^{\prime }$ is as announced: $f^{\prime }(\sigma )\cap f^{\prime }(\tau )=f(\sigma )\cap f(\tau )\setminus \{x,y\}$ and every other intersection remains unchanged. This concludes the proof of Theorem 4.

We now prove Theorem 3. First, note that the odd-dimensional case reduces to the even-dimensional one. Indeed, for every $k\ge 2$, if $ℳ$ is a compact, $(k-1)$-connected, $(2k-1)$-dimensional PL manifold (possibly with boundary), then $ℳ\times [0,1]$ is a compact, $(k-1)$-connected, $2k$-dimensional PL manifold (possibly with boundary). Moreover, ${\beta }_k(ℳ\times [0,1];{\mathbb{Z}}_2)={\beta }_k(ℳ;{\mathbb{Z}}_2)$ and any homological minor of $ℳ$ is a homological minor of $ℳ\times [0,1]$. If the statement holds for $d$ even and $b\in \mathbb{N}$ with some $N(b,d)$, then it holds with $d-1$ and $b$ by putting $N(d-1,b):=N(d,b)$. So let us now consider the even-dimensional case.

Let $k\ge 2$ and $b\in \mathbb{N}$, and let $ℳ$ be a compact, $(k-1)$-connected, $2k$-dimensional PL manifold (possibly with boundary). Let us fix $N$ and suppose that $K={\mathrm{\Delta }}_N^{(k)}$ is a homological minor of $ℳ$. By Lemma 8, there exist a triangulation $T$ of $ℳ$ and a (simplicial) homological almost-embedding $C_{\ast }(K)\to C_{\ast }(T)$. Actually, letting $S:=T^{(k)}$, we have that there exists a homological almost-embedding $a:C_{\ast }(K;{\mathbb{Z}}_2)\to C_{\ast }(S;{\mathbb{Z}}_2)$.

We apply Theorem 9 with $L=S$. Condition (i) holds with $T=S$ and $f$ the identity, so Condition (ii) also holds. Hence, there exists a triangulation $R$ of ${ℝ}^{2k}$, a simplicial map $g:S\to R$ in general position, and a map $\alpha$ that sends each $k$-face of $S$ to an element of $H_k(ℳ;{\mathbb{Z}}_2)$ such that any two non-adjacent $k$-faces $\sigma ,\tau \in S$ intersect evenly if and only if ${\cap }_{ℳ}(\alpha (\sigma ),\alpha (\tau ))=0$. We let $\tilde{\alpha }:C_k(S)\to H_k(ℳ;{\mathbb{Z}}_2)$ denote the linear extension of $\alpha$.

Consider the chain map $b:C_{\ast }(K;{\mathbb{Z}}_2)\to C_{\ast }(R;{\mathbb{Z}}_2)$ defined by $b=g_{\mathrm{\#}}\circ a$. Note that $b$ is nontrivial since $a$ is nontrivial and $g$ is a simplicial map. Moreover, the fact that $b$ is a chain map in general position follows from three observations:

• $\mathrm{■}$

  since $g$ is a simplicial map in general position, $g_{\mathrm{\#}}$ is a chain map in general position,

• $\mathrm{■}$

  since $a$ is a homological almost-embedding, it is also a chain map in general position, and

• $\mathrm{■}$

  the composition of a homological almost-embedding and a chain map in general position is a chain map in general position.

Notice that for $N\ge 2k+3$, not every independent $k$-faces of $K$ can have images under $b$ that intersect evenly. Indeed Theorem 4 would then imply that $K$ is a homological minor of ${ℝ}^{2k}$, which would contradict the homological van Kampen-Flores theorem (Theorem 2). We use Ramsey’s theorem to show that this contradiction can be reached for some subcomplex of $K$.

So consider two non-adjacent $k$-faces $\sigma ,\tau \in K$ and put $a(\sigma )={\sigma }_1+{\sigma }_2+\mathrm{\dots }+{\sigma }_s$ and $a(\tau )={\tau }_1+{\tau }_2+\mathrm{\dots }+{\tau }_t$. Since $a$ is a homological almost-embedding, $\mathrm{supp}(a(\sigma ))$ and $\mathrm{supp}(a(\tau ))$ are disjoint, and ${\sigma }_i$ and ${\tau }_j$ are thus non-adjacent for every $(i,j)\in [s]\times [t]$. Hence, given $(i,j)\in [s]\times [t]$, $g({\sigma }_i)$ and $g({\tau }_j)$ intersect evenly if and only if ${\cap }_{ℳ}(\alpha ({\sigma }_i),\alpha ({\tau }_j))=0$. We can thus count the intersections of $b(\sigma )$ and $b(\tau )$ (the following equalities are modulo $2$ and $\text{Card}\left(\right)$ denotes the cardinal):

Let $r={\beta }_k(ℳ;{\mathbb{Z}}_2)$. The map $\beta :C_k(K)\to H_k(ℳ;{\mathbb{Z}}_2)$ defined by $\beta =\tilde{\alpha }\circ a$ induces a coloring of the $k$-simplices of $K$ by the (at most $2^r$) elements of $H_k(M;{\mathbb{Z}}_2)$. Let $N^{\prime }$ denote the number of vertices of $\mathrm{sd}{\mathrm{\Delta }}_{2k+2}^{(k)}$. By the hypergraph Ramsey theorem, for $N$ large enough (as a function of $r$ and $k$) there exists a subset $W$ of $N^{\prime }$ vertices in $K$ such that $\beta$ is constant over all $k$-simplices of $K[W]$; let us denote by $\mathrm{\square }$ this constant value. In particular, for every $k$-faces $\sigma ,\tau$ of $K[W]$ such that $\sigma$ and $\tau$ are not adjacent, we have, modulo $2$, $\text{Card}\left(b(\sigma )\cap b(\tau )\right)={\cap }_{ℳ}(\beta ({\sigma }_1),\beta ({\tau }_1))={\cap }_{ℳ}(\mathrm{\square },\mathrm{\square })$. Let us fix a bijection from the vertices of $\mathrm{sd}{\mathrm{\Delta }}_{2k+2}^{(k)}$ to $W$ and extend it to a chain map $j:C_{\ast }\left(\mathrm{sd}{\mathrm{\Delta }}_{2k+2}^{(k)}\right)\to C_{\ast }(K[W])$. Also, let $h:C_{\ast }\left({\mathrm{\Delta }}_{2k+2}^{(k)}\right)\to C_{\ast }\left(\mathrm{sd}{\mathrm{\Delta }}_{2k+2}^{(k)}\right)$ denote the subdivision chain map, where each $i$-face of ${\mathrm{\Delta }}_{2k+2}^{(k)}$ is mapped to the sum of the $i$-faces of $\mathrm{sd}{\mathrm{\Delta }}_{2k+2}^{(k)}$ that it contains. In particular, for every $k$-face $\sigma$ of ${\mathrm{\Delta }}_{2k+2}^{(k)}$, the chain $h(\sigma )$ is supported on $k!$ $k$-faces of $\mathrm{sd}{\mathrm{\Delta }}_{2k+2}^{(k)}$.

Let us examine the properties of $b\circ j\circ h$. First, it is a nontrivial chain map (because $b$, $j$ and $h$ are). Moreover, $j\circ h$ is a homological almost-embedding (since $j$ and $h$ are), and its composition with the chain map in general position $b$ yields a chain map in general position. Furthermore, any two non-adjacent $k$-faces $\sigma ,\tau \in {\mathrm{\Delta }}_{2k+2}^{(k)}$ have images under $b\circ j\circ h$ that intersect evenly. To see this, let us put $j\circ h(\sigma )={\sigma }_1+{\sigma }_2+\mathrm{\dots }+{\sigma }_s$ and $j\circ h(\tau )={\tau }_1+{\tau }_2+\mathrm{\dots }+{\tau }_s$. Since $j\circ h$ is a homological almost-embedding, $\mathrm{supp}(j\circ h(\sigma ))$ and $\mathrm{supp}(j\circ h(\tau ))$ are disjoint. It follows that for every $i,j\in [s]$ the $k$-simplices ${\sigma }_i$ and ${\tau }_j$ are non-adjacent. We therefore have, modulo 2,

To sum up, the cardinal of $b\circ j\circ h(\sigma )\cap b\circ j\circ h(\tau )$ has the same parity as ${\cap }_{ℳ}(\mathrm{\square },\mathrm{\square })s^2$. Since $s=k!$ is even, $\sigma$ and $\tau$ have images under $b\circ j\circ h$ that intersect evenly.

To conclude, $b\circ j\circ h$ is a nontrivial chain map in general position from ${\mathrm{\Delta }}_{2k+2}^{(k)}$ to $R$ such that independent faces have images that intersect evenly. By Theorem 4 this means that ${\mathrm{\Delta }}_{2k+2}^{(k)}$ is a homological minor of ${ℝ}^{2k}$, a contradiction with Theorem 2. Thus, for $N$ large enough, the initial hypothesis that ${\mathrm{\Delta }}_N^{(k)}$ is a homological minor of $ℳ$ cannot be true.

Each relation between parameters of a set system yields a relation between their graded analogues. From Levi’s inequality we get the following inequality between the graded Helly and Radon numbers (defined in Section 1.1.1):

It follows from the definitions of graded parameters that each one is a non-decreasing function that converges to the ungraded parameter (possibly $\mathrm{\infty }$). We notice that if a graded Helly number is asymptotically sublinear then it is bounded:

Let us finally consider topological set systems with slowly growing homological shatter function and ground set with a forbidden homological minor.