Conditions for the existence of approximations to the constant sheaf

This is a result I proved a while back as part of a larger project that never went anywhere. It turns out there might be people interested in the result for its own sake, so this seems a reasonable place to get it written down.

In my thesis, I introduced the idea of an approximation to a cellular sheaf, and gave some randomized algorithms for constructing spectrally good approximations based on the literature for graph sparsification. While these algorithms could give bounds on the total dimension of the stalks of the approximating sheaf, they didn’t have any control over what happened locally—there might be critical parts of the complex where stalks are forced to stay the same dimension. So I was interested in anything that might help better understand the constraints on the stalk dimensions of a sheaf approximation, particularly in the case of approximations to constant sheaves.

For completeness, I’ll give a definition here: a $k$-approximation to the constant sheaf $\underline{V}$ on a complex $X$ is a sheaf $\Fc$ together with a sheaf morphism $a: \underline{V} \to \Fc$ for which the following hold:

1. $a$ is an isomorphism on stalks over cells of dimension $\leq k$
2. $a$ is surjective on stalks over cells of dimension $> k$
3. $H^k a$ is an isomorphism (note that condition 1 implies that $H^i a$ is an isomorphism for $i < k$).

This is most immediately interesting when $k = 0$, so that an approximation to the constant sheaf on a graph $G$ has the same vertex stalks but may have lower-dimensional edge stalks, while still having the same space of global sections. The constant sheaf on a graph gives a local algorithm for verifying the constancy of a $0$-cochain; this algorithm requires communication of a $\dim V$-dimensional vector over each edge. An approximation to the constant sheaf also provides such an algorithm, but potentially requiring less communication per edge.

If you choose the natural basis, the $0$-Laplacian of an approximation to the constant sheaf $\underline{\R^k}$ on a graph (or really any sheaf that admits a map $\underline{\R^k} \to \Fc$) is a matrix-weighted graph Laplacian. This is the obvious Laplacian matrix for a graph where each edge has a $k \times k$ symmetric positive semidefinite weight matrix—the off-diagonal blocks $L_{ij} = -W_{ij}$ are negatives of the corresponding weight matrices, and the diagonal blocks $L_{ii} = \sum_{i \sim j} W_{ij}$ are sums of the weight matrices for edges incident to a node. These types of Laplacians have been studied in control theory settings for reasons that were always a little opaque to me. Like a lot of academic engineering literature, it’s hard for me to tell if the applications described are genuine or just descriptions of conceivable-but-not-realistic scenarios where precisely this mathematical object would be called for. To be clear, I’m not one to judge here—while I describe directions for applicability of sheaves, I’ve seldom felt that I had a clear-cut application that wouldn’t be possible without sheaf theory. Actually, this result is a little nice in that regard, since the sheaf language does help prove something about matrix-weighted graphs that I don’t see a nice way to prove otherwise.

Anyway, the setup here is that we’ve chosen a dimension $k$ for the stalks of the constant sheaf as well as a fixed graph (or cell complex). We’ll also choose a dimension vector $d$ defining the dimensions of the stalks of $\Fc$ over each edge $e$. The question is for which dimension vectors it is possible to construct an approximation to the constant sheaf $\underline{\R^k}$. Here’s the answer:

Proposition.

Let $G$ be a graph, and let $d$ be a dimension vector for $G$ with $d_v = k$ for all vertices $v$. The following are equivalent:

1. There exists a 0-approximation to the constant sheaf $a: \underline{\R^k} \to \mathcal F$ on $G$ with dimension vector $d$
2. For every partition $\mathcal P$ of the vertices of $G$, $$\sum_{e \in E(\mathcal P)} d_e \geq k(\left| {\mathcal P}\right| - 1)$$
3. There exists a collection of $k$ spanning trees of $G$ such that each edge $e$ of $G$ is contained in at most $d_e$ trees in the collection.

Proof. We’ll show (1) $\Rightarrow$ (2) by counting dimensions. Consider the quotient graph $G / \mathcal P$ which has one node for each set $U \in \mathcal P$ and an edge between $U$ and $V$ if there exist $u \in U, v \in V$ such that there is an edge between $u$ and $v$ in $G$. We can take the pushforward $p_* \underline{\Fc}$ over the quotient map $p: G \to G / \mathcal P$. For $U \in V(G / \mathcal P)$, we have $p_*\underline{\Fc}(U) = H^0(U ; \underline{\Fc})$. This has dimension at least $k$, so $C^0(G/\mathcal P; p_*\Fc) \geq \abs{\mathcal P}k$. Meanwhile, the edge stalks of $p_*\underline{\Fc}$ are just direct sums of edge stalks of $\Fc$, so $C^1(G/\mathcal P; p_*\Fc) = \sum_{e \in E(\mathcal P)} d_e$. The pushforward of a sheaf preserves its space of global sections, so $\dim H^0(G/\mathcal P;p_* \Fc) = k$. Since $H^0 = \ker \delta$, we must have $\dim H^0 \geq \dim C^0 - dim C^1$, so

$$\abs{\mathcal P} k - \sum_{e \in E(\mathcal P)} d_e \leq \dim C^0(G/\mathcal P; p_*\Fc) - \dim C^1(G/\mathcal P;p_*\Fc) \leq k.$$

We can use a tree-packing result proved independently by Tutte¹ and Nash-Williams² for the implication (2) $\Rightarrow$ (3). They showed that there exists a set of $k$ edge-disjoint spanning trees in a multigraph $G$ if and only if for every partition $\mathcal P$ of $V(G)$, $E(\mathcal P) \geq k(\abs{\mathcal P} - 1)$. Replacing each edge of $G$ with $d_e$ edges yields an equivalence with condition (2).

Finally, (3) $\Rightarrow$ (1) by considering for each spanning tree $T_j$ the inclusion map $\iota: T_i \to G$ and pushing the constant sheaf $\underline{\R}$ on $T_j$ forward to get a collection of $k$ sheaves $\Fc_j = \iota_* \underline{\R}$ on $G$. Then each $\Fc_j$ is an approximation to $\underline{\R}$ on $G$, so that $\Fc = \bigoplus_j \Fc_j$ is an approximation to $\underline{\R^k} = \underline{\R}^{\oplus k}$ on $G$. The requirement on the spanning tree packing ensures that the dimension vector of $\Fc$ is bounded above by $d$; taking a direct sum with a sheaf supported only on edges can then make the dimension vector exactly $d$. $\:\:\blacksquare$

A matroid-theoretic generalization of the Tutte/Nash-Williams theorem proven by Edmonds³ allows us to generalize this to higher-dimensional complexes, although I’m not sure if anyone cares:

Let $X$ be an $n$-dimensional regular cell complex, and let $d$ be a dimension vector on $X$ with $d_\sigma = k$ for $\dim(\sigma) < n$. The following are equivalent:

1. There exists an $(n-1)$-approximation $a: \underline{\R^k} \to \Fc$ on $X$ with dimension vector $d$.
2. For every subcomplex $Q$ of $X$ with $Q^{n-1} = X^{n-1}$, $$\sum_{\substack{\dim \sigma = n \ \sigma \in X \setminus Q}}d_\sigma \geq k \left( \dim {H}^{n-1}(Q;\R) - \dim H^{n-1}(X;\R) \right)$$
3. There exists a collection of $k$ spanning $n$-acycles of $X$, such that for each $n$-cell $\sigma$ of $X$, $\sigma$ is contained in at most $d_\sigma$ of the acycles.

But the people who might actually be interested in this are concerned with matrix-weighted graphs, so I’ll translate it into that language:

Let $G$ be a graph, and suppose we want to assign $k \times k$ weight matrices $W_{ij}$ to produce a matrix-weighted Laplacian $L$. Then the following are equivalent:

1. There exists a choice of weight matrices $W_{ij}$ with $\rank(W_{ij}) = r_{ij}$ such that $\dim \ker L = k$
2. For every partition $\mathcal P$ of the vertices of $G$, $$\sum_{i\sim j | \mathcal P_i \neq \mathcal P_j} r_{ij} \geq k(\left| {\mathcal P}\right| - 1)$$
3. There exists a collection of $k$ spanning trees of $G$ such that each edge $i \sim j$ is contained in at most $r_{ij}$ trees.

So what does this mean? In one sense, this theorem might be kind of disappointing. It’s not hard to show that the spanning tree condition implies that an approximation to the constant sheaf is possible, since it basically ignores all of the extra degrees of freedom we get from being able to choose bases other than the standard basis for $\R^k$. One might hope that by cleverly choosing subspaces to project onto, it might be possible to get by with lower-dimensional edge stalks (or lower-rank weight matrices) than you might if you restricted yourself to axis-aligned projections. But this isn’t the case: the obvious sufficient condition is also necessary.

Now, there’s still a reasonable hope that even if varying the basis doesn’t buy you anything combinatorially, it might still buy you something spectrally: for a given dimension vector, it might be that it’s possible to get a bigger spectral gap with general matrix weights than with axis-aligned projections. This is similar to the argument that better-than-Ramanujan matrix-weighted expander graphs might exist.

I also have a hunch that existence of an approximation to the constant sheaf is a generic condition, so that if it’s possible to construct one, it’s also easy. I don’t have a rigorous argument for this, but unless some sort of catastrophic alignment of constraints happens, matrices will generically have the maximum rank possible.

What I do like about this result is that it has an essential and nontrivial use of sheaf theory. Using the framework of approximations to the constant sheaf made proving (1) $\Rightarrow$ (2) straightforward. I’m not sure there’s a nice way to prove the equivalent statement in terms of matrices. I’ll take that as a win for algebraic topology.

1. W. T. Tutte, “On the Problem of Decomposing a Graph into n Connected Factors,” Journal of the London Mathematical Society, vol. s1-36, no. 1, pp. 221–230, 1961, doi: 10.1112/jlms/s1-36.1.221. ↩

2. C. St. J. A. Nash-Williams, “Edge-Disjoint Spanning Trees of Finite Graphs,” Journal of the London Mathematical Society, vol. s1-36, no. 1, pp. 445–450, Jan. 1961, doi: 10.1112/jlms/s1-36.1.445. ↩

3. J. Edmonds, “Lehman’s switching game and a theorem of Tutte and Nash-Williams,” Journal of Research of the National Bureau of Standards-B. Mathematics and Mathematical Physics, vol. 69B, no. 1 and 2, p. 73, Jan. 1965, doi: 10.6028/jres.069B.005. ↩