Improved fractional Helly from stepping-up

A fractional Helly theorem for $(K,b)$ -free covers was previously established by the third author [Reference Patáková39] with a worse fractional Helly number: the assumption is that a positive fraction of the m-tuples have nonempty intersection, where for $\dim K>1$ , m is a hypergraph Ramsey number depending on b and K.

To prove Theorem 1.6 it therefore suffices to show that if a positive fraction of the $(\mu (K)+1)$ -tuples intersect, then a positive fraction of the m-tuples intersect. This follows from successive applications of Theorem 1.5. (Note that the existence of a finite m established in [Reference Patáková39, Theorem 2.3] is essential to ensure this process terminates; additionally, the implicit bound on $\beta $ derived from [Reference Patáková39, Theorem 2.3] changes during this process.)

Improved $(p,q)$ -theorem from improved fractional Helly

Theorem 1.4 is an immediate consequence of Theorem 1.6 and the results of Alon et al. [Reference Alon, Kalai, Matoušek and Meshulam3]. In essence, Alon et al. show that if an intersection closed set system has fractional Helly number at most m, then the set system also satisfies a $(p,q)$ -theorem for the range $p \geq q \geq m$ (see Theorems 8(i) and 9 and the discussion in $\S 2.1$ in [Reference Alon, Kalai, Matoušek and Meshulam3]). Thus, Theorem 1.4 follows by applying Theorem 1.6 to the intersection closure $\mathcal {F}^\cap := \{ \cap _{S \in \mathcal {G}} S \colon \mathcal {G} \subset \mathcal {F}\}$ , observing that $\mathcal {F}^\cap $ is a $(K,b)$ -free cover if and only if $\mathcal {F}$ is.

A hypergraph supersaturation argument

For a more detailed explanation, it is convenient to reformulate the problem in terms of hypergraphs. Given a $(K,b)$ -free cover $\mathcal {F}$ , we consider a hypergraph $\mathcal {H}$ whose vertices correspond to the members of $\mathcal {F}$ and whose edges correspond to the intersecting m-tuples in $\mathcal {F}$ . This makes $\mathcal {H}$ a dense m-uniform hypergraph on $|\mathcal {F}|$ vertices and $\pi _m(\mathcal {F})> \delta \binom {|\mathcal {F}|}{m}$ edges. The Erdős–Simonovits (supersaturation) theorem [Reference Erdős and Simonovits20] implies that there exist at least $\rho \binom {|\mathcal {F}|}{mt}$ distinct vertex subsets of size $mt$ that each span a complete m-partite subhypergraph with parts of size t. Here t is any fixed positive integer, and crucially, the fraction $\rho> 0$ depends only on m, t, and $\delta $ . In other words, the positive edge density of $\mathcal {H}$ ensures a positive density of complete m-partite subhypergraphs with parts of size t.

Returning to the $(K,b)$ -free cover $\mathcal {F}$ , each complete m-partite subhypergraph in $\mathcal {H}$ corresponds to a collection of disjoint subfamilies $\mathcal {F}_1, \dots , \mathcal {F}_m \subset \mathcal {F}$ , with $|\mathcal {F}_i| = t$ , such that $S_1\cap \cdots \cap S_m\neq \emptyset $ for every choice $S_i\in \mathcal {F}_i$ . This is a familiar intersection pattern originating in the colorful Helly theorem [Reference Bárány7].

Colored $(K,b)$ -free covers and a weak colorful Helly theorem

This leads us to introduce a colorful analogue of $(K,b)$ -free covers. Given a collection of nonempty set systems $\mathcal {F}_1, \mathcal {F}_2, \ldots , \mathcal {F}_m$ , a subfamily $\mathcal {G} \subset \bigcup _{i=1}^m \mathcal {F}_i$ is called colorful if $\mathcal {G}$ contains at most one member from each $\mathcal {F}_i$ . We define an m-colored (K,b)-free cover in a simplicial complex X to be a finite family $\mathcal {F} = \mathcal {F}_1 \sqcup \mathcal {F}_2 \sqcup \cdots \sqcup \mathcal {F}_m$ of subcomplexes of X such that:

1. (i) K is a forbidden homological minor of X, and

2. (ii) $\tilde {\beta }_j(\bigcap _{S \in \mathcal {G}}S) < b$ for all $0\leq j < \dim (K)$ and all nonempty colorful subfamilies $\mathcal {G} \subseteq \mathcal {F}$ .

Returning to the relation between the family $\mathcal {F}$ and the m-regular hypergraph $\mathcal {H}$ , every subset of $mt$ vertices that spans a complete m-partite subhypergraph with parts of size t corresponds to a subfamily of $\mathcal {F}$ that can be colored to form an m-colored $(K,b)$ -free cover where each color class has size t and every colorful subfamily has nonempty intersection. We prove that each such family has the following property:

Note that the definition of colored $(K,b)$ -free cover does not impose any condition on the noncolorful subfamilies, as this is not needed for the proof of Theorem 2.1.

Stepping up from weak colorful Helly and supersaturation

Our main result, Theorem 1.5, now follows from Theorem 2.1 via double counting and supersaturation.

Specifically, let $\mathcal {F}$ be a $(K,b)$ -free cover with at least $\delta \binom {|\mathcal {F}|}{m}$ intersecting m-tuples, where $m> \mu (K)$ , and let $t = t(b,K,m)$ be the integer provided by Theorem 2.1. By the supersaturation argument outlined above, there are at least $\rho \binom {|\mathcal {F}|}{mt} m$ -colored subfamilies of $\mathcal {F}$ that satisfy the hypothesis of Theorem 2.1.

For each such m-colored subfamily, we apply Theorem 2.1 to find an intersecting subfamily of size $2m-\mu (K)$ . Since $2m-\mu (K) \geq m+1$ , this implies the existence of an intersecting $(m+1)$ -tuple within that subfamily. By summing over all such subfamilies and correcting for the number of times a given intersecting $(m+1)$ -tuple is counted, we conclude that there are at least $\gamma \binom {|\mathcal {F}|}{m+1}$ intersecting $(m+1)$ -tuples, where $\gamma>0$ depends only on $\delta $ , b, m, and K.

The full details of this argument are provided in Section 6.

The example

Let us consider a simplified situation where we are given a 3-colored family $\mathcal {F} = \mathcal {F}_1 \sqcup \mathcal {F}_2 \sqcup \mathcal {F}_3$ of open connected sets in $\mathbb {R}^2$ such that the intersection of any colorful subfamily is nonempty and connected. We show that if $|\mathcal {F}_i| = 5$ for every $1\leq i \leq 3$ , then there exist four members in $\mathcal {F}$ with nonempty intersection.

Encoding the family in a graph

The colorful subfamilies of $\mathcal {F}$ are encoded by a graph $G = (V,E)$ , defined on the vertex set $V = \{(a_1,a_2,a_3)\in \mathbb {N}^3 : 1\leq a_i \leq 5\}$ . Vertices u and v are connected by an edge, $e = uv$ , whenever their Euclidean distance satisfies $|u-v|=1$ . It is convenient to view G as a 1-dimensional complex realized in $\mathbb {R}^3$ with its vertices on the integer lattice, and edges parallel to the coordinate axes, forming a 3-dimensional grid (see Figure 2, left).

Figure 2

On the left: A planar projection of the graph G from the $[5]\times [5] \times [5]$ grid in $\mathbb {Z}^3$ . The edges of $K_5$ are mapped by $g_{\bullet }$ to the blue paths. On the right: Connecting points $p_u$ and $p_v$ by a constrained path $\gamma _{uv}.$

Figure 2 Long description

The left panel displays a three-dimensional lattice representing a 5 times 5 times 5 grid in Z super 3. Black dots mark the vertices of the grid. Thick blue lines trace specific paths along the edges of the grid, primarily concentrated on the top and left faces of the cube structure. The right panel shows three overlaping sets and a constrained path. The sets are colored red, green and blue, where the blue set has two connected components and intersects both red and green set. Moreover, the intersection of red and green is connected. The vertices of the constrained path are placed at the two distinct connected components of the intersection of all three sets, while the path is fully contained in the intersection of red and green set.

We introduce a map $\psi $ that assigns a colorful subfamily of $\mathcal {F}$ to every cell (vertex or edge) in G. First, we label the sets in $\mathcal {F}$ such that $\mathcal {F}_j = \{ S_{1,j}, \dots , S_{5,j}\}$ for $1\leq j \leq 3$ . The mapping $\psi $ is then defined as follows:

• For a vertex $v = (a,b,c)$ , $\psi $ selects one set from each family: $\psi (v) = \{S_{a,1}, S_{b,2}, S_{c,3}\}$ .

• For an edge $uv$ , $\psi $ assigns the intersection of the endpoint values: $\psi (uv) = \psi (u) \cap \psi (v)$ .

Note that $\psi $ establishes a bijection between the vertices of G and the maximal colorful subfamilies of $\mathcal {F}$ , and for any edge e, we have $|\psi (e)| = 2$ . Furthermore, for any two edges e and $e'$ , the size $|\psi (e) \cup \psi (e')|$ is determined by the relative geometric alignment of e and $e'$ in the grid:

• If e and $e'$ are contained in a common axis-parallel line, then $\psi (e) = \psi (e')$ , and so $|\psi (e) \cup \psi (e')| = 2$ .

• If e and $e'$ are contained in a common axis-parallel plane, but not in a common axis-parallel line, then $\psi (e)$ and $\psi (e')$ have exactly one member in common, and so $|\psi (e) \cup \psi (e')| = 3$ .

Most important for us is the following property:

• If e and $e'$ are not contained in any common axis-parallel plane, then $\psi (e)$ and $\psi (e')$ are disjoint, and so $|\psi (e) \cup \psi (e')| = 4$ .

(Chain) maps

To prove that some four members of $\mathcal {F}$ intersect, we construct maps relating $K_5$ , G, and $\mathbb {R}^2$ . In this simple example, these could be (PL) maps, but it turns out to be convenient in the general case to work with chain maps. We thus use chain maps also for this simple example.

The first chain map

The first is a map $f_{\bullet } \colon C_{\bullet }(G) \to C_{\bullet }(\mathbb {R}^2)$ , defined as follows:

• On vertices (0-chains): For a vertex v in G we select a representative point $p_v \in \mathbb {R}^2$ contained in the common intersection of the sets in $\psi (v)$ . We set $f_0(v) = p_v$ .

• On edges (1-chains): Consider an edge $uv$ in G. The points $p_u$ and $p_v$ are both contained in the intersection of the subfamily $\psi (uv)$ . Since this intersection is assumed to be connected, there exists a path $\gamma _{uv}$ connecting $p_u$ to $p_v$ entirely within $\bigcap _{S\in \psi (uv)}S$ . We set $f_1(uv) = \gamma _{uv}$ .

The construction of $f_{\bullet }$ is completed by extending linearly to arbitrary chains. A key feature of this construction is that for every cell $\sigma \in G$ , the image $f_{\bullet }(\sigma )$ is contained within the intersection $\bigcap _{S\in \psi (\sigma )} S$ . This containment property is what we refer to when we say that $f_{\bullet }$ is constrained by the colorful family $\mathcal {F}$ (see Figure 2).

The second chain map

We now define the second chain map $g_{\bullet } \colon K_5 \to G$ , which sends the vertices $v_1, \dots , v_5$ of $K_5$ to the vertices $(1,1,1), \dots , (5,5,5)$ along the main diagonal in the geometric representation of G. Each edge $v_iv_j$ in $K_5$ is mapped to a specific path in G connecting the corresponding diagonal vertices. These paths are constructed to satisfy the following crucial geometric property:

• For any two disjoint edges e and $e'$ in $K_5$ , if an axis-parallel plane P contains an edge $\tau $ from the path $g_1(e)$ , then P does not contain any edge $\tau '$ from the path $g_1(e')$ .

We omit the explicit construction of these paths for the moment, referring instead to Figure 2.

The new intersection appears

To find four intersecting members in $\mathcal {F}$ , we compose $f_{\bullet }$ with $g_{\bullet }$ to obtain the chain map $h_{\bullet } \colon C_{\bullet }(K_5) \to C_{\bullet }(\mathbb {R}^2)$ as in the diagram above. Because $K_5$ is a forbidden homological minor of $\mathbb {R}^2$ , $h_{\bullet }$ must result in two disjoint edges e and $e'$ in $K_5$ whose images $h_1(e)$ and $h_1(e')$ overlap. Since $h_{\bullet }$ factors through $C_{\bullet }(G)$ , there must exist specific edges $\tau $ from the path $g_1(e)$ and $\tau '$ from the path $g_1(e')$ whose images $f_1(\tau )$ and $f_1(\tau ')$ intersect at some point $p\in \mathbb {R}^2$ . Recalling that $f_{\bullet }$ is constrained by $\mathcal {F}$ , the point p must lie in the intersection of all the sets in the subfamily $\psi (\tau ) \cup \psi (\tau ')$ . By the geometric property highlighted above, these grid edges $\tau $ and $\tau '$ do not lie in any common axis-parallel plane; thus $|\psi (\tau ) \cup \psi (\tau ')| = 4$ . Therefore p is contained in the intersection of four distinct members of $\mathcal {F}$ .

Roadmap for the general case

Stepping back, we see that the only property of $\mathbb {R}^2$ that we used above was that $K_5$ is a forbidden homological minor. In fact, the same argument demonstrates that for $K = K_5$ , $b=1$ , and $m=3$ , the parameter $t(b,K,m)$ in Theorem 2.1 satisfies $t\leq 5$ . The proof for general K, b, and m (given in Section 6) follows the same basic structure. Let us highlight the main steps that need to be established along the way:

The grid complex

The colorful subfamilies of $\mathcal {F}$ are encoded by a suitable grid complex whose vertices lie on the integer grid $\mathbb {Z}^m$ . We introduce the general grid complex $G[n]^m$ in Section 3.1, where we also establish terminology and basic properties that will be used throughout the paper. The crucial notion of a subgrid is introduced in Section 3.2, while the encoding of colorful subfamilies via grid complexes is given in Section 3.3.

The first chain map: Constrained chain maps

Our goal is to build chain maps as in the diagram from the proof sketch above, though certain technical obstacles arise that were absent in the simplified setting.

For instance, when $b>1$ , the intersection of a colorful subfamily may have several connected components, making it impossible to find a constrained path $\gamma _{uv}$ as we did previously. However, since we have an absolute bound on the number of connected components (bounded by b), we can ensure – provided the color classes $\mathcal {F}_i$ are sufficiently large – that many of the vertex images lie in the same connected component. This allows us to construct some constrained paths.

Our strategy is to construct enough paths (as well as higher-dimensional chains) to form a sufficiently large subgrid $G'$ from which we can construct a chain map $f_{\bullet } \colon C_{\bullet }(G') \to C_{\bullet }(X)$ that is constrained by $\mathcal {F}$ . This notion is formally defined in Section 4.1.

The existence of such a constrained chain map (Lemma 4.1) is achieved using Ramsey-type arguments – specifically, the Gallai–Witt Theorem [Reference Witt43] on monochromatic subsets of $\ \mathbb {Z}^m$ – which we use to establish a vanishing lemma for subgrids in Section 4.2. We then prove the existence of constrained chain maps in Section 4.3.

The second chain map: Generic chain maps into grid complexes

To complete the diagram, we also require a chain map $g_{\bullet } \colon C_{\bullet }(K) \to C_{\bullet }( G')$ . This map should be generic in the sense that disjoint faces of K are mapped to chains with no common alignments along axis-parallel hyperplanes. As in the sketch above, this allows us to control the size of the union of the colorful subfamilies represented by different cells $\sigma $ and $\tau $ in $G'$ . See Section 5.1 for the precise statements (Lemma 5.1 and Corollary 5.2).

We give a canonical method for constructing $g_{\bullet }$ based on the stair convexity of Bukh et al. [Reference Bukh, Matoušek and Nivasch10]. Stair convexity was originally introduced to study extremal problems on point configurations in $\mathbb {R}^d$ ; to our knowledge, it has not previously been used in the context of grid complexes and chain maps. This adaptation is defined in Section 5.2.

Our application of stair convexity requires (a somewhat tedious) verification that it is compatible with the boundary operator in grid complexes. This verification and the construction of $g_{\bullet }$ are carried out in Sections 5.3 and 5.4.

Cells and chains

For every integer $a \in [n]$ we use interchangeably the notations $[a,a] = \{a\}$ to denote the corresponding $0$ -cell in $G[n]$ . For all integers $a,b \in [n]$ with $a < b$ , we let $[a,b] = [b,a]$ denote the 1-chain with $\mathbb {Z}_2$ coefficients

$$\begin{align*}\left.\begin{array}{r} {[a,b]}\\{[b,a]}\end{array}\right\} := [a,a+1] + [a+1,a+2] + \cdots + [b-1,b].\end{align*}$$

Notice that for any distinct integers $a,b,c \in [n]$ we have $[a,c] = [a,b] + [b,c]$ , as we work with $\mathbb {Z}_2$ -coefficients. Every k-cell $\sigma $ in $G[n]^m$ can be written as the product of exactly $(m-k) 0$ -cells and $k 1$ -cells

$$\begin{align*}\sigma = [a_1,b_1] \times [a_2,b_2] \times \cdots \times [a_m,b_m],\end{align*}$$

where $1\leq a_i \leq b_i \leq a_i+1 \leq n$ . When the i-th factor of a cell $\sigma $ is a $0$ -cell, we say that the i-th coordinate of $\sigma $ is constant. Note that $G[n]^m$ is a regular cell complex of dimension m.

The terminology introduced for simplicial complexes carries directly over to grid complexes. A k-chain is a sum of k-cells in $G[n]^m$ with coefficients in $\mathbb {Z}_2$ . The support of a chain $\sigma $ , denoted $\operatorname {\mathrm {supp}}(\sigma )$ , is the set of cells with nonzero coefficients in $\sigma $ , and two chains, $\sigma $ and $\tau $ , have overlapping supports if there is a cell in $\operatorname {\mathrm {supp}}(\sigma )$ that intersects a cell in $\operatorname {\mathrm {supp}}(\tau )$ . We formulate the following simple observation for future reference.

Products and boundaries

The usual (Cartesian) product $\times $ of a $k_1$ -cell of $G[n]^{m_1}$ and a $k_2$ -cell of $G[n]^{m_2}$ is a $(k_1+k_2)$ -cell of $G[n]^{m_1+m_2}$ . We extend this operation to chains by putting

$$\begin{align*}(\sigma_1 + \cdots + \sigma_{\ell_1}) \times (\tau_1 + \cdots + \tau_{\ell_2}) \; := \; \sum_{i=1}^{\ell_1}\sum_{j=1}^{\ell_2} \sigma_i \times \tau_j.\end{align*}$$

We denote the null chain (with empty support) by $0$ and clarify that for any chain $\sigma $ we have $\sigma \times 0 = 0 \times \sigma = 0$ . We can now define the boundary of a cell of $G[n]^m$ recursively, as follows (working over $\mathbb {Z}_2$ ):

$$\begin{align*}\begin {array}{rrcl} \mathbf {(0-cells)} & \quad\partial \{a\} &\ \ :=\ \ & 0 \qquad \qquad \qquad \qquad (\text{the null chain})\\\mathbf {(1-cells)} & \quad\partial [a,a+1] &\ \ :=\ \ & \{a\}+\{a+1\}\\\mathbf {(\ge 2-cells)} & \quad\partial (\sigma \times \tau ) &\ \ :=\ \ & \partial \sigma \times \tau + \sigma \times \partial \tau \\ \end {array} \end{align*}$$

The definition of $\partial $ extends from k-cells to k-chains by linearity. A simple induction on the dimension yields that $\partial \circ \partial = 0$ . In fact, $\partial $ coincides with the standard boundary operator on $G[n]^m$ when viewed as a regular cell complex. For a subcomplex G of a grid complex, we write $C_{\bullet }\left (G\right )$ for the chain complex defined by the chains of G equipped with $\partial $ .

The case $k=m$

Fix $m\geq 1$ , $b\geq 1$ , and $\ell \ge 2$ . Let $n \geq \ell $ be an integer and let $\mathbf {1}$ denote $(1,1,\ldots , 1) \in \mathbb {Z}^m$ . Given $x, y \in V(G[n]^m)$ we write $x \preceq y$ if $x_i \le y_i$ for $i=1,\ldots , m$ . For any two vertices $x \preceq y$ we define the m-chain $\operatorname {\mathrm {box}}_m(x,y) \in C_m(G[n]^m)$ by

$$\begin{align*}\operatorname{\mathrm{box}}_m(x,y) = \begin{cases} 0 & \text{ if } x_i=y_i \text{ for some } i,\\ [x_1,y_1] \times [x_2,y_2] \times \cdots \times [x_m,y_m] & \text{ otherwise.} \end{cases} \end{align*}$$

For illustration see Figure 4 (right). Note that $\operatorname {\mathrm {box}}_m(x,y)$ is nonzero if and only if x and y do not share any coordinate (i.e., they do not lie in a common axis-parallel hyperplane).

For the linear map $h:C_m(G[n]^m) \to \left (\mathbb {Z}_2\right )^b$ to vanish on a subgrid $\Gamma $ of size $\ell $ , it suffices to have

(4.2) $$ \begin{align} h(\operatorname{\mathrm{box}}_m(\Gamma(z), \Gamma(z + \mathbf{1}))) = 0 \text{ for all } z \in V(G[\ell -1]^m). \end{align} $$

This is because $C_m(G[\ell ]^m)$ is spanned by the set of elementary cells $\{\operatorname {\mathrm {box}}_m(z, z + \mathbf {1}) \colon z \in V(G[\ell -1]^m)\}$ , and $\operatorname {\mathrm {box}}_m(\Gamma (z), \Gamma (z + \mathbf {1})) = \Gamma _{\bullet }(\operatorname {\mathrm {box}}_m(z, z + \mathbf {1}))$ .

To apply Proposition 4.3, we consider the vertex coloring $\chi _h \colon V(G[n]^m) \to \left (\mathbb {Z}_2\right )^b$ defined by

$$\begin{align*}\chi_h(y) := h(\operatorname{\mathrm{box}}_m(\mathbf{1},y)).\end{align*}$$

Proof of the claim

By (4.2), it suffices to show that $h(\operatorname {\mathrm {box}}_m(u,v)) = 0$ for all $u = \Gamma (z)$ and $v=\Gamma (z+\mathbf {1})$ with $z \in V(G[\ell -1]^m)$ . Let W denote the set of corners of $\operatorname {\mathrm {box}}_m(u,v)$ , that is,

$$\begin{align*}W= \{(w_1,\ldots, w_m)\colon w_i \in \{u_i, v_i\} \text{ for every } i \in [m]\}. \end{align*}$$

By the inclusion-exclusion principle (and since we work with coefficients in $\mathbb Z_2$ ), we have

$$\begin{align*}\operatorname{\mathrm{box}}_m(u,v) = \sum_{w \in W} \operatorname{\mathrm{box}}_m(\mathbf{1}, w).\end{align*}$$

In other words, $\operatorname {\mathrm {box}}_m(u,v)$ is the sum of the boxes anchored at $\mathbf {1}$ with opposite corners in W. Applying the linear map h to both sides, and using the hypothesis that $\chi _h$ is constant on the image of $\Gamma $ , we get

$$\begin{align*}h(\operatorname{\mathrm{box}}_m(u,v)) = \sum_{w \in W} h(\operatorname{\mathrm{box}}_m(\mathbf{1}, w)) = \sum_{w \in W} \chi_h(w) = \chi_h(u)|W| = 0,\end{align*}$$

where the last equality holds because $|W| = 2^m$ is even (for $m\geq 1$ ).

To complete the proof of Lemma 4.2 for the case $k=m$ , let $N = N(b,m,m,\ell )$ be the constant $N(m,\ell , 2^{b})$ from Proposition 4.3. For any $n \ge N$ and any linear map $h:C_m(G[n]^m) \to (\mathbb {Z}_2)^b$ , applying Proposition 4.3 to the vertex coloring $\chi _h$ ensures the existence of a monochromatic subgrid $\Gamma $ of size $\ell $ in $G[n]^m$ . By Claim 4.4, h vanishes on $\Gamma $ .

The case $1 \leq k < m$

The proof of the general case essentially reduces to multiple instances of the full-dimensional case by restricting attention to every possible axis-parallel k-flat that passes through vertices of $G[n]^m$ .

It will be convenient to introduce some further notation. Fix integers $1\leq k<m$ , $b\geq 1$ , and $\ell \ge 2$ . For every vertex $y = (y_1, \dots , y_m) \in G[n]^m$ and an index set $I \in \binom {[m]}k$ , we define the k-chain $\operatorname {\mathrm {chn}}_I(y)$ as follows. Let $x = (x_1, \dots , x_m)$ be the vertex defined by

$$\begin{align*}x_j = \begin{cases} 1 & \text{if } j \in I, \\ y_j & \text{if } j \notin I. \end{cases} \end{align*}$$

We then set

$$\begin{align*}\operatorname{\mathrm{chn}}_I(y) = \begin{cases} 0 & \text{if } y_j = 1 \text{ for some } j \in I,\\ [x_1,y_1] \times \cdots \times [x_m,y_m] & \text{otherwise.} \end{cases} \end{align*}$$

For illustration see Figure 5. Note that if $j \notin I$ , then $[x_j, y_j] = [y_j, y_j]$ is simply the vertex $y_j$ (a 0-chain). Thus, $\operatorname {\mathrm {chn}}_I(y)$ is a product of k 1-chains (the intervals $[1, y_j]$ for $j \in I$ ) and $(m-k)$ 0-chains (the vertices $y_j$ for $j \notin I$ ), making it a k-chain. It is nonzero if and only if $y_j \neq 1$ for all $j \in I$ . (Note that if we allowed $k=m$ , then $\operatorname {\mathrm {chn}}_{[m]}(y)$ would coincide with $\operatorname {\mathrm {box}}_m(\mathbf {1},y)$ .)

Figure 5

The 2-chain $\operatorname {\mathrm {chn}}_{\{1,2\}}\big ( (3,4,4) \big )$ in blue, and the 2-chain $\operatorname {\mathrm {chn}}_{\{1,3\}}\big ( (3,4,4) \big )$ in red.

To apply Proposition 4.3, we consider the vertex coloring $\rho _h \colon V(G[n]^m) \to (\mathbb {Z}_2)^{b\binom {m}{k}}$ defined by

$$\begin{align*}\rho_h(y) := \big(h(\operatorname{\mathrm{chn}}_I(y))\big)_{I \in \binom{[m]}k}. \end{align*}$$

We think of $\rho _h(y)$ as a vector of $\binom {m}{k}$ elements from $\left (\mathbb {Z}_2\right )^b$ , indexed by the subsets $I\in \binom {[m]}{k}$ . We denote the component of $\rho _h(\cdot )$ corresponding to the index set I by $[\rho _h(\cdot )]_I$ .

Proof of the claim

For a point $a = (a_1, \dots , a_m) \in \mathbb {Z}^m$ and a subset $I\in \binom {[m]}{k}$ define the axis-parallel k-flat $F_I(a)$ by

$$\begin{align*}F_I(a) = \{(x_1, \dots, x_m) \in \mathbb{R}^m : x_i = a_i\; \forall i\notin I\}.\end{align*}$$

This is the k-flat passing through a where the coordinates indexed by I vary, while the others remain fixed. Note that for any vertex $z \in V(G[\ell ]^m)$ , the intersection $G[\ell ]^m \cap F_I(z)$ is isomorphic to $G[\ell ]^k$ , and similarly $G[n]^m\cap F_I(\Gamma (z))$ is isomorphic to $G[n]^k$ .

Furthermore, for any vertex $w\in V(G[\ell ]^m) \cap F_I(z)$ , the support of the chain $\operatorname {\mathrm {chn}}_I(\Gamma (w))$ is contained in $V(G[n])^m \cap F_I(\Gamma (z))$ . Thus restricting $\Gamma $ and h to the flats $F_I(z)$ and $F_I(\Gamma (z))$ reduces the problem to the full-dimensional case (within that k-flat). Since $[\rho _h(\Gamma (w))]_I = h\big (\operatorname {\mathrm {chn}}_I(\Gamma (w))\big )$ is constant for all $w\in V(G[\ell ]^m) \cap F_I(z)$ , Claim 4.4 implies that h vanishes on the restriction of $\Gamma $ to $F_I(z)$ . Since the elementary k-cells in these flats span all of $C_k(G[\ell ]^m)$ as we vary z and I, we conclude that h vanishes on all of $\Gamma $ .

Returning to the proof of Lemma 4.2, let $N = N(m,\ell , q)$ be the constant from Proposition 4.3 with $q = 2^{b\binom {m}{k}}$ . For any $n \ge N$ and for any linear map $h : C_k(G[n]^m) \to \left (\mathbb {Z}_2\right )^b$ , applying Proposition 4.3 to the vertex coloring $\rho _h$ ensures the existence of a monochromatic subgrid $\Gamma $ in $G[n]^m$ of size $\ell $ . By Claim 4.5, h vanishes on $\Gamma $ . This completes the proof of the subgrid lemma.

Setting up the induction

It remains to prove that property $(P_\ell )$ holds under the hypotheses of Lemma 4.1 for $\ell =0,1,\ldots , d$ . The proof is by induction.

First, for each colorful subfamily $\mathcal {G} \subset \mathcal {F}$ , we fix (arbitrarily) a basis for $\tilde {H}_j(\bigcap \mathcal {G})$ , $0\leq j < d$ . (Here, we view the reduced homology groups as $\mathbb {Z}_2$ -vector spaces.) Since $\tilde {\beta }_j(\bigcap \mathcal {G}) < b$ by assumption, we may view each $\tilde {H}_j(\bigcap \mathcal {G})$ as a subspace of $(\mathbb {Z}_2)^b$ . These bases (and subspaces) remain fixed for the remainder of the proof.

To verify the base case $(P_0)$ , we let $\Gamma ^{(0)} : V(G[t_0]^m)\to V(\text{Grd}_{\mathcal {F}})$ be the identity map. (Recall that $\text{Grd}_{\mathcal {F}} = G[t_0]^m$ .) For each vertex $v\in G[t_0]^m$ we fix a vertex $p_v$ in the intersection $\bigcap \psi (v)$ of the maximal colorful family associated with v (which is nonempty by hypothesis). We define the chain map $f^{(0)}_{\bullet } : C_{\bullet }(Y_0) \to C_{\bullet }(X)$ by setting $f^{(0)}_{{\bullet }}(v) = p_v$ for every vertex v of $G[t_0]^m$ . This map is clearly nontrivial and constrained by $\mathcal {F}$ .

The induction step

Let $0\leq \ell < d$ and suppose property $(P_\ell )$ is satisfied. That is, we are given a subgrid $\Gamma ^{(\ell )} : V(G[t_\ell ]^m) \to V(\text{Grd}_{\mathcal {F}})$ and a nontrivial chain map

$$\begin{align*}f^{(\ell)}_{\bullet}: C_{\bullet}(Y_\ell) \to C_{\bullet}(X)\end{align*}$$

such that $\operatorname {\mathrm {supp}} f^{(\ell )}_{\bullet }(\sigma ) \subset \bigcap \psi \big ( \Gamma ^{(\ell )}_{{\bullet }}(\sigma ) \big )$ for every cell $\sigma \in Y_\ell $ .

For any $(\ell +1)$ -cell $\sigma $ in $G[t_\ell ]^m$ , the chain $\Gamma ^{(\ell )}_{{\bullet }}(\sigma )$ is well-defined. By Claim 3.2, the support of this chain has the same affine span in $\text{Grd}_{\mathcal {F}}$ as the support of its boundary $\Gamma ^{(\ell )}_{{\bullet }}(\partial \sigma )$ . Therefore we have

(4.3) $$ \begin{align} \operatorname{\mathrm{supp}} f^{(\ell)}_{{\bullet}}(\partial\sigma) \subset \bigcap \psi\big(\Gamma^{(\ell)}_{{\bullet}}(\partial \sigma) \big) = \bigcap \psi\big( \Gamma^{(\ell)}_{{\bullet}}(\sigma) \big). \end{align} $$

Now we define a linear map $h: C_{\ell +1}(G[t_\ell ]^m) \to (\mathbb {Z}_2)^b$ by setting, for any $(\ell +1)$ -dimensional cell $\sigma $ ,

(4.4) $$ \begin{align} h(\sigma) := \left[ f^{(\ell)}_{\bullet}(\partial\sigma) \right] \in \tilde{H}_{\ell}\left(\bigcap \psi\big( \Gamma^{(\ell)}_{\bullet}(\sigma) \big) \right) \subset (\mathbb{Z}_2)^b, \end{align} $$

and extending h linearly. In other words, $h(\sigma )$ equals the homology class of the image $f^{(\ell )}_{\bullet }(\partial \sigma )$ in the $\ell $ -dimensional (reduced) homology group of $\bigcap \psi \big ( \Gamma ^{(\ell )}_{\bullet }(\sigma ) \big )$ , which we can view as an element in $(\mathbb {Z}_2)^b$ .

By Claim 4.6, h vanishes on some subgrid $\Phi : V(G[t_{\ell +1}]^m) \to V(G[t_\ell ]^m)$ of size $t_{\ell +1}$ . We set

$$\begin{align*}\Gamma^{(\ell+1)} := \Gamma^{(\ell)}\circ \Phi,\end{align*}$$

and note that $\Gamma ^{(\ell +1)}$ is indeed a vertex map from $V(G[t_{\ell +1}]^m)$ to $V(\text{Grd}_{\mathcal {F}})$ , making $\Gamma ^{(\ell +1)}$ a subgrid of $\text{Grd}_{\mathcal {F}}$ of size $t_{\ell +1}$ . Note also that the induced chain map $\Gamma ^{(\ell +1)}_{\bullet }$ satisfies $\Gamma ^{(\ell +1)}_{\bullet } = \Gamma _{\bullet }^{(\ell )} \circ \Phi _{\bullet }$ .

Let $\tau \in G[t_{\ell +1}]^m$ be a cell of dimension $(\ell +1)$ . Since h vanishes on $\Phi $ , we have $h\big (\Phi _{\bullet }(\tau )\big ) = 0$ . By definition of h, this means the homology class of $f_{\bullet }^{(\ell )}\big (\partial \Phi _{\bullet }(\tau )\big )$ is zero, that is,

(4.5) $$ \begin{align} \left[ f^{(\ell)}_{\bullet}\big(\partial\Phi_{\bullet}(\tau)\big) \right] = 0 \in \tilde{H}_{\ell}\left(\bigcap \psi \big(\Gamma^{(\ell)}_{\bullet}(\Phi_{\bullet}(\tau))\big)\right). \end{align} $$

Using that $\Phi _{\bullet }$ is a chain map and the fact that $\Gamma ^{(\ell +1)}_{\bullet } = \Gamma _{\bullet }^{(\ell )} \circ \Phi _{\bullet }$ , this rewrites as

(4.6) $$ \begin{align} \left[ f^{(\ell)}_{\bullet} \big( \Phi_{\bullet}(\partial\tau) \big) \right]=0\in \tilde{H}_{\ell}\left(\bigcap \psi \big( \Gamma^{(\ell+1)}_{\bullet}(\tau)\big)\right). \end{align} $$

For a cell $\sigma \in G[t_{\ell +1}]^m$ of dimension at most $\ell $ , we set

(4.7) $$ \begin{align} f_{\bullet}^{(\ell+1)}(\sigma) := f_{{\bullet}}^{(\ell)}\big( \Phi_{\bullet}(\sigma) \big). \end{align} $$

For a cell $\tau \in G[t_{\ell +1}]^m$ of dimension $(\ell +1)$ , equation (4.6) reveals that $f_{\bullet }^{(\ell +1)}(\partial \tau )$ is a boundary in $C_{\ell }\left ( \bigcap \psi \big ( \Gamma ^{(\ell +1)}_{\bullet }(\tau ) \big ) \right )$ . We choose some arbitrary $\alpha \in C_{\ell +1} \left ( \bigcap \psi \big ( \Gamma ^{(\ell +1)}_{\bullet }(\tau ) \big ) \right )$ such that $\partial \alpha = f_{\bullet }^{(\ell +1)}(\partial \tau )$ , and set

(4.8) $$ \begin{align} f^{(\ell+1)}_{\bullet}(\tau) := \alpha. \end{align} $$

Therefore $f^{(\ell +1)}_{\bullet }$ is indeed a chain map from $C_{\bullet }(Y_{\ell +1})$ to $C_{\bullet }\left (X\right )$ . Note that by (4.7), it follows that $f_{\bullet }^{(\ell +1)}$ is nontrivial because $f_{\bullet }^{(\ell )}$ is nontrivial and $\Phi $ , being a subgrid, maps each vertex to a single vertex. Moreover, by construction $f^{(\ell +1)}_{\bullet }$ and $\Gamma ^{(\ell +1)}$ satisfy $(P_{\ell +1})$ . This concludes the proof of the induction step and of Lemma 4.1.

Examples

At one end, $\operatorname {\mathrm {sc}}_0^m(a)$ is a vertex on the main diagonal of $G[n]^m$ . At the other end, $\operatorname {\mathrm {sc}}_m^m(a_1, \dots , a_{m+1})$ is an m-dimensional box. Let us examine some simple examples for intermediate values of k. For $m=2$ and $k=1$ we have

$$\begin{align*}\operatorname{\mathrm{sc}}_1^{2}(a,b) = \operatorname{\mathrm{sc}}^1_0(a) \times [a,b] + \operatorname{\mathrm{sc}}^1_1(a,b) \times \{b\} = \{a\} \times [a,b] + [a,b] \times \{b\}\end{align*}$$

which is a rectilinear path from $(a,a)$ to $(b,b)$ with a bend at $(a,b)$ . Similarly, $\operatorname {\mathrm {sc}}_1^3(a, b)$ is a rectilinear path from $(a,a,a)$ to $(b,b,b)$ with bends at $(a,a,b)$ and $(a,b,b)$ :

$$\begin{align*}\begin{aligned} & \operatorname{\mathrm{sc}}_1^3(a, b)\\ & = \operatorname{\mathrm{sc}}^{2}_0(a) \times [a,b] + \operatorname{\mathrm{sc}}^{2}_1(a,b) \times \{b\}\\ & = \{a\} \times \{a\} \times [a,b] \\ & \quad \quad + \left(\{a\} \times [a,b] + [a,b] \times \{b\}\right) \times \{b\}\\ & = \{a\}\times \{a\} \times [a,b] \\ & \quad \quad + \{a\} \times [a,b] \times \{b\} \\ & \quad \quad \quad \quad+ [a,b] \times \{b\} \times \{b\} \end{aligned}\end{align*}$$

For $m=3$ and $k=2$ , we get the following $2$ -chain:

$$\begin{align*}\begin{aligned} & \operatorname{\mathrm{sc}}_2^3(a, b, c) \\ & = \operatorname{\mathrm{sc}}^{2}_1(a, b)\times [b,c] + \operatorname{\mathrm{sc}}^{2}_2(a, b, c) \times \{c\}\\ & = \{a\}\times [a,b] \times [b,c] \\ & \quad \quad + [a,b] \times \{b\} \times [b,c]\\ & \quad\quad\quad\quad + [a,b] \times [b,c] \times \{c\}, \end{aligned}\end{align*}$$

Case $\mathbf {m=k\geq 2}$

Here, we proceed by induction on m, and assume that the statement holds for $m-1$ :

$$\begin{align*}\partial \operatorname{\mathrm{sc}}^{m-1}_{m-1}(a_1, \dots, a_{m}) = \sum_{i=1}^{m} \operatorname{\mathrm{sc}}^{m-1}_{m-2}(a_1, \dots, \widehat{a_i}, \dots, a_{m}).\end{align*}$$

From the definition of $\partial $ we get

$$\begin{align*}\begin{aligned} & \ \partial \operatorname{\mathrm{sc}}^m_m(a_1, \dots, a_{m+1})\\ = & \ \ \partial \left(\operatorname{\mathrm{sc}}^{m-1}_{m-1}(a_1, \dots, a_m)\times [a_m, a_{m+1}]\right)\\ = & \ \underbrace{\left(\partial \operatorname{\mathrm{sc}}^{m-1}_{m-1}(a_1, \dots, a_m)\right) \times [a_m, a_{m+1}]}_\alpha + \underbrace{\operatorname{\mathrm{sc}}^{m-1}_{m-1}(a_1, \dots, a_m) \times \left(\{a_m\} + \{a_{m+1}\}\right)}_\beta \end{aligned} \end{align*}$$

We then use the induction hypothesis to rewrite $\alpha $ as

$$\begin{align*}\alpha = \sum_{i=1}^{m} \underbrace{\operatorname{\mathrm{sc}}^{m-1}_{m-2}(a_1, \dots, \widehat{a_i}, \dots, a_{m}) \times [a_m, a_{m+1}]}_{\alpha_i}.\end{align*}$$

and use Lemma 5.6 to partially expand $\beta $ into

$$\begin{align*}\beta = \underbrace{\operatorname{\mathrm{sc}}^{m-1}_{m-1}(a_1, \dots, a_m) \times \{a_{m}\}}_{\beta_0} + \sum_{i=1}^m\underbrace{\operatorname{\mathrm{sc}}^{m-1}_{m-1}(a_1, \dots, \widehat{a_i}, \dots, a_{m+1}) \times \{a_{m+1}\}}_{\beta_i}\end{align*}$$

For $i \le m-1$ , we have $\alpha _i + \beta _i = \operatorname {\mathrm {sc}}^{m}_{m-1}(a_1, \dots , \widehat {a_i}, \dots , a_{m+1})$ by the recursive definition of $\operatorname {\mathrm {sc}}^{m}_{m-1}$ . For the same reason, for any $a \in [n]$ ,

(5.2) $$ \begin{align} \begin{aligned} \operatorname{\mathrm{sc}}^{m}_{m-1}(a_1, \dots, a_{m-1},a) = & \ \operatorname{\mathrm{sc}}^{m-1}_{m-2}(a_1, \dots, a_{m-1}) \times [a_{m-1},a] \\ & \ + \operatorname{\mathrm{sc}}^{m-1}_{m-1}(a_1, \dots, a_{m-1},a) \times \{a\}. \end{aligned} \end{align} $$

Since the $a_i$ are pairwise distinct, we have $[a_m,a_{m+1}] = [a_{m-1},a_m] + [a_{m-1},a_{m+1}]$ . Using Identity (5.2) once with $a=a_m$ and once with $a=a_{m+1}$ , we obtain

$$\begin{align*}\alpha_m = \operatorname{\mathrm{sc}}^{m}_{m-1}(a_1, \dots,a_m) + \beta_0 + \operatorname{\mathrm{sc}}^{m}_{m-1}(a_1, \dots, a_{m-1},a_{m+1}) + \beta_m.\end{align*}$$

Altogether,

$$\begin{align*}\partial \operatorname{\mathrm{sc}}^m_m(a_1, \dots, a_{m+1}) = \alpha+\beta = \sum_{i=1}^{m+1} \operatorname{\mathrm{sc}}^{m}_{m-1}(a_1, \dots, \widehat{a_i}, \dots, a_{m+1})\end{align*}$$

as claimed.

General case

We now prove the general case by induction on m. So assume the statement holds for $m-1$ and consider $1 \le k \le m$ . We already handled the case $k=m$ , so let us consider the case $k<m$ , for which we can use the recursive definition of $\operatorname {\mathrm {sc}}^m_k$ :

$$\begin{align*}\operatorname{\mathrm{sc}}^m_k(a_1, \ldots, a_{k+1}) = \operatorname{\mathrm{sc}}^{m-1}_{k-1}(a_1, \ldots, a_k) \times [a_k,a_{k+1}]+\ \operatorname{\mathrm{sc}}^{m-1}_k(a_1, \ldots, a_{k+1}) \times \{a_{k+1}\}.\end{align*}$$

We thus have

$$\begin{align*}\begin{aligned} \partial \operatorname{\mathrm{sc}}^m_k(a_1, \ldots, a_{k+1}) &= \left(\partial \operatorname{\mathrm{sc}}^{m-1}_{k-1}(a_1, \ldots, a_k)\right) \times [a_k,a_{k+1}]\\& \quad + \operatorname{\mathrm{sc}}^{m-1}_{k-1}(a_1, \ldots, a_k) \times \left(\{a_k\} + \{a_{k+1}\}\right)\\& \quad + \left(\partial \operatorname{\mathrm{sc}}^{m-1}_k(a_1, \ldots, a_{k+1})\right) \times \{a_{k+1}\} \end{aligned}\end{align*}$$

Using the induction hypothesis for $\operatorname {\mathrm {sc}}^{m-1}_{k-1}$ and $\operatorname {\mathrm {sc}}^{m-1}_{k}$ , we obtain

$$\begin{align*} \partial \operatorname{\mathrm{sc}}^m_k(a_1, \ldots, a_{k+1}) = & \ \sum_{i=1}^{k} \operatorname{\mathrm{sc}}^{m-1}_{k-2}(a_1, \dots, \widehat{a_i}, \dots, a_{k})\times [a_k,a_{k+1}] \\& + \sum_{i=1}^{k+1} \operatorname{\mathrm{sc}}^{m-1}_{k-1}(a_1, \dots, \widehat{a_i}, \dots, a_{k+1}) \times \{a_{k+1}\}\\& + \operatorname{\mathrm{sc}}^{m-1}_{k-1}(a_1, \ldots, a_k) \times \left(\{a_k\} + \{a_{k+1}\}\right)\\= & \ \sum_{i=1}^{k} \underbrace{\operatorname{\mathrm{sc}}^{m-1}_{k-2}(a_1, \dots, \widehat{a_i}, \dots, a_{k})\times [a_k,a_{k+1}]}_{\alpha_i} \\& + \sum_{i=1}^{k} \underbrace{\operatorname{\mathrm{sc}}^{m-1}_{k-1}(a_1, \dots, \widehat{a_i}, \dots, a_{k+1}) \times \{a_{k+1}\}}_{\beta_i}\\ & + \underbrace{\operatorname{\mathrm{sc}}^{m-1}_{k-1}(a_1, \ldots, a_k) \times \{a_k\}}_{\beta_0}\\ \end{align*}$$

For $i \le k-1$ , we recognize the recursive definition of $\operatorname {\mathrm {sc}}^{m}_{k-1}$ in

$$\begin{align*}\alpha_i + \beta_i = \operatorname{\mathrm{sc}}^{m}_{k-1}(a_1, \dots, \widehat{a_i}, \dots, a_{k+1}).\end{align*}$$

Since the elements $a_1, \ldots , a_{k+1}$ are pairwise distinct, $[a_k,a_{k+1}] = [a_{k-1},a_k] + [a_{k-1},a_{k+1}]$ and we can split $\alpha _k$ and use the recursive definition of $\operatorname {\mathrm {sc}}^{m}_{k-1}$ on each part:

$$\begin{align*}\begin{aligned} \alpha_k = & \ \operatorname{\mathrm{sc}}^{m-1}_{k-2}(a_1, \dots, a_{k-1}) \times [a_{k-1},a_{k+1}] + \operatorname{\mathrm{sc}}^{m-1}_{k-2}(a_1, \dots, a_{k-1})\times [a_{k-1},a_{k}]\\ = & \ \left(\operatorname{\mathrm{sc}}^{m}_{k-1}(a_1, \dots, a_{k-1},a_{k+1}) + \beta_k\right) + \left(\operatorname{\mathrm{sc}}^{m}_{k-1}(a_1, \dots, a_{k-1},a_{k}) + \beta_0\right). \end{aligned}\end{align*}$$

Altogether,

$$\begin{align*}\operatorname{\mathrm{sc}}^m_k(a_1, \ldots, a_{k+1}) = \sum_{i=1}^{k+1} \operatorname{\mathrm{sc}}^{m}_{k-1}(a_1, \dots, \widehat{a_i}, \dots, a_{k+1}),\end{align*}$$

as claimed.

Finally, we are now in position to prove the “Picasso Lemma”.

Proof of Lemma 5.1

Label the vertices of K as $v_1, v_2, \dots , v_n$ . For every simplex $\{v_{i_1}, \dots , v_{i_{k+1}}\} \in K$ with $1\leq i_1 < i_2 <\cdots < i_{k+1}\leq n$ , we define:

$$\begin{align*}g(\{v_{i_1}, \dots, v_{i_{k+1}}\}) \; := \; \operatorname{\mathrm{sc}}^m_k(i_1, \dots, i_{k+1}). \end{align*}$$

We extend g linearly into a map $g_{\bullet } \colon C_{\bullet }(K) \to C_{\bullet }(G[n]^m)$ . Proposition 5.5 guarantees that $g_{\bullet }$ commutes with the boundary operator, making it a valid chain map. Furthermore, since every vertex $v_a\in V(K)$ is mapped to a single vertex $\{a\}\times \cdots \times \{a\}\in G[n]^m$ , the map is nontrivial.

To show that $g_{\bullet }$ is generic, let $\sigma $ and $\tau $ be a pair of disjoint simplices in K, and consider arbitrary cells $\sigma ' \in \operatorname {\mathrm {supp}}(g_{\bullet }(\sigma ))$ and $\tau ' \in \operatorname {\mathrm {supp}}(g_{\bullet }(\tau ))$ . Since $m> \mu (K)$ (implies $\dim \sigma + \dim \tau < m$ ), it follows that $\dim \sigma ' + \dim \tau ' < m$ . By Observation 3.1, there is at least one coordinate, $x_i$ , that is constant for both cells. However, they cannot share the same constant value in this coordinate (i.e., $x_i = a$ is impossible for both), because Corollary 5.4 would imply that both $\sigma $ and $\tau $ contain the vertex $v_a$ , contradicting their disjointness. Thus, the pair $\{g_{\bullet }(\sigma ), g_{\bullet }(\tau )\}$ is generic.