11 The \((k, \ell )\)-count matroid
Let \(V\) be a finite set, let \(K_V\) be the complete graph on \(V\), and let \(k\) and \(\ell \) be non-negative integers with \(\ell {\lt} 2k\). We call a set \(I \subseteq E(K_V)\) \((k, \ell )\)-sparse if the graph on \(V\) with edge set \(I\) is \((k, \ell )\)-sparse (definition 3.1). In this section we show that the \((k, \ell )\)-sparse subsets of \(E(K_V)\) are the independent sets of a matroid on \(E(K_V)\), the \((k, \ell )\)-count matroid. In section 10.3 we took its case \((k, \ell ) = (2, 3)\) as the definition of the planar rigidity matroid \(\mathcal{R}(V)\). Theorem 10.19 identifies \(\mathcal{R}(V)\) with the rigidity matroid of a framework of \(K_V\).
The count matroid goes back to Lorea and, independently, to White and Whiteley. Whiteley [ Whi96 , Proposition A.1.1 ] proves it in the generality of hypergraphs and credits both. Lee and Streinu [ LS08 , Theorem 2 ] prove a version for multigraphs. Their proof rests on the structure of tight sets, which we also use.
Tight sets are as in section 3, where the paragraph after definition 3.4 relates them to Jordán’s critical sets. Let \(G\) be a \((k, \ell )\)-sparse graph on \(V\). Following Lee and Streinu, who speak of the induced subgraphs, we call a \((k, \ell )\)-tight set of \(G\) a component of \(G\) if no other \((k, \ell )\)-tight set of \(G\) contains it.
A family of subsets of a finite set is the family of independent sets of a matroid if it contains the empty set, is closed under taking subsets, and has the augmentation property: if \(I\) and \(J\) are members with \(|I| {\lt} |J|\), then \(I \cup \{ e\} \) is a member for some \(e \in J \setminus I\). For the \((k, \ell )\)-sparse subsets of \(E(K_V)\) the first two properties are immediate. We prove the third in section 11.1 (lemma 11.6), and define the matroid in section 11.2.
We sketch the proof of the augmentation property. Let \(I\) and \(J\) be \((k, \ell )\)-sparse with \(|I| {\lt} |J|\), and let \(G\) be the graph on \(V\) with edge set \(I\). Since \(\ell {\lt} 2k\), two distinct vertices that lie in a tight set of \(G\) lie in exactly one component of \(G\). So two distinct components share at most one vertex, and no edge lies inside both. Suppose that \(I \cup \{ e\} \) is \((k, \ell )\)-sparse for no \(e \in J \setminus I\). Then the endpoints of each edge of \(J \setminus I\) lie in a tight set of \(G\), and hence in a component. Inside each of these components, \(J\) has at most as many edges as \(I\), since the component is tight in \(G\) and \(J\) is sparse. Every other edge of \(J\) is an edge of \(I\). Hence \(|J| \le |I|\), a contradiction.
Lee and Streinu also decide whether a graph is \((k, \ell )\)-sparse by an algorithm, the \((k, \ell )\)-pebble game, which we formalize in section 13.
11.1 Components and augmentation
The first lemma is the case \(\ell {\lt} 2k\) of theorem 3.14, and it follows from Lee and Streinu’s Theorem 5(1) [ LS08 ] . From it we obtain the component that contains a given set of at least two vertices. We then show that two distinct components share at most one vertex, which is their Theorem 5(2). These lemmas and lemma 11.2 give the augmentation property.
Let \(V\) be finite, let \(\ell {\lt} 2k\), and let \(G\) be a \((k, \ell )\)-sparse graph on \(V\). Let \(s, t \subseteq V\) be \((k, \ell )\)-tight in \(G\), and suppose that two distinct vertices \(u\) and \(v\) lie in both \(s\) and \(t\). Then \(s \cup t\) and \(s \cap t\) are \((k, \ell )\)-tight in \(G\).
Since \(u\) and \(v\) lie in \(s \cap t\), we have \(|s \cap t| \ge 2\), and so \(\ell {\lt} 2k \le k\, |s \cap t|\). Hence theorem 3.14 applies.
The next lemma is one direction of Lee and Streinu’s Corollary 6 [ LS08 ] .
Let \(G\) be a \((k, \ell )\)-sparse graph on a set \(V\), which need not be finite, and let \(u\) and \(v\) be distinct vertices that are not adjacent in \(G\). Let \(G + uv\) be obtained from \(G\) by adding the edge \(uv\). If \(G + uv\) is not \((k, \ell )\)-sparse, then some set containing \(u\) and \(v\) is \((k, \ell )\)-tight in \(G\).
Since \(G + uv\) is not sparse, there is a set \(S \subseteq V\) with \(\ell \le k\, |S|\) and \(|E_{G + uv}[S]| + \ell {\gt} k\, |S|\) (definition 3.1). If \(u\) or \(v\) lies outside \(S\), then \(G + uv\) and \(G\) have the same edges inside \(S\), and this contradicts the sparsity of \(G\) at \(S\).
So \(u\) and \(v\) lie in \(S\). Since \(uv\) is not an edge of \(G\), the set \(S\) spans exactly one more edge of \(G + uv\) than of \(G\). Hence \(k\, |S| {\lt} |E_{G}[S]| + 1 + \ell \), while the sparsity of \(G\) gives \(|E_{G}[S]| + \ell \le k\, |S|\). So \(|E_{G}[S]| + \ell = k\, |S|\), that is, \(S\) is tight in \(G\).
By lemma 11.1, the tight sets of a sparse graph that contain two given vertices are closed under union. We therefore consider the union of all tight sets that contain a given set of vertices.
Let \(V\) be finite, let \(G\) be a graph on \(V\), and let \(X \subseteq V\). We write \(C_G(X)\) for the union of all sets that contain \(X\) and are \((k, \ell )\)-tight in \(G\). If there is no such set, then \(C_G(X)\) is empty.
Let \(V\) be finite, let \(\ell {\lt} 2k\), and let \(G\) be a \((k, \ell )\)-sparse graph on \(V\). Let \(X \subseteq V\) have at least two elements, and suppose that some \((k, \ell )\)-tight set of \(G\) contains \(X\). Then \(C_G(X)\) is \((k, \ell )\)-tight in \(G\).
Let \(\mathcal{F}\) be the family of tight sets of \(G\) that contain \(X\). It is finite, since \(V\) is, and it is non-empty by hypothesis. Choose distinct vertices \(u\) and \(v\) in \(X\). Every member of \(\mathcal{F}\) contains \(u\) and \(v\), so the union of two members of \(\mathcal{F}\) is tight (lemma 11.1) and is again a member of \(\mathcal{F}\). By induction on the number of members, the union of all members of \(\mathcal{F}\) is a member of \(\mathcal{F}\). This union is \(C_G(X)\), which is therefore tight.
Under these hypotheses, \(C_G(X)\) is therefore the largest tight set of \(G\) that contains \(X\). It is a component of \(G\): a tight set that contains \(C_G(X)\) also contains \(X\), and so it is contained in \(C_G(X)\).
Let \(V\) be finite, let \(\ell {\lt} 2k\), and let \(G\) be a \((k, \ell )\)-sparse graph on \(V\). Let \(X, Y \subseteq V\) each have at least two elements. Suppose that some \((k, \ell )\)-tight set of \(G\) contains \(X\), and that \(Y \subseteq C_G(X)\). Then \(C_G(Y) = C_G(X)\). In particular, two distinct components of \(G\) share at most one vertex, and so no edge.
The set \(C_G(X)\) is tight (lemma 11.4). It contains \(Y\), so it is one of the sets whose union is \(C_G(Y)\). Hence \(C_G(X) \subseteq C_G(Y)\). Since some tight set contains \(Y\), the set \(C_G(Y)\) is tight as well (lemma 11.4). Both \(C_G(X)\) and \(C_G(Y)\) contain \(Y\), which has at least two elements, so their union is tight (lemma 11.1). This union contains \(X\), so it is contained in \(C_G(X)\). Hence \(C_G(Y) \subseteq C_G(X)\).
For the last claim, let \(C\) be a component of \(G\) with at least two vertices. Then \(C \subseteq C_G(C)\), and \(C_G(C)\) is tight (lemma 11.4). Since no other tight set contains \(C\), we have \(C = C_G(C)\). If distinct vertices \(u\) and \(v\) lie in \(C\), then the first claim, with \(X = C\) and \(Y = \{ u, v\} \), gives \(C = C_G(\{ u, v\} )\). So two components that share \(u\) and \(v\) are both equal to \(C_G(\{ u, v\} )\).
We can now prove the augmentation property.
Let \(V\) be finite, let \(\ell {\lt} 2k\), and let \(I, J \subseteq E(K_V)\) be \((k, \ell )\)-sparse with \(|I| {\lt} |J|\). Then there is an edge \(e \in J \setminus I\) such that \(I \cup \{ e\} \) is \((k, \ell )\)-sparse.
Let \(G\) and \(H\) be the graphs on \(V\) with edge sets \(I\) and \(J\), so that \(G\) and \(H\) are \((k, \ell )\)-sparse. Suppose, to the contrary, that \(I \cup \{ e\} \) is \((k, \ell )\)-sparse for no \(e \in J \setminus I\). Let \(e = uv\) be an edge in \(J \setminus I\). Since \(e \notin I\), the vertices \(u\) and \(v\) are not adjacent in \(G\), and \(G + uv\) is the graph on \(V\) with edge set \(I \cup \{ e\} \). It is not sparse, so some tight set of \(G\) contains \(u\) and \(v\) (lemma 11.2). Let \(C_e = C_G(\{ u, v\} )\). This set contains \(u\) and \(v\), and it is tight in \(G\) (lemma 11.4).
Let \(\mathcal{C}\) be the family of the sets \(C_e\), for \(e \in J \setminus I\). An edge \(xy\) of \(K_V\) lies inside at most one member of \(\mathcal{C}\). Indeed, if \(x\) and \(y\) lie in \(C_e\), then \(C_G(\{ x, y\} ) = C_e\) (lemma 11.5). Let \(I_0\) and \(J_0\) be the sets of edges of \(I\) and of \(J\) that lie inside no member of \(\mathcal{C}\). Then \(I\) is the disjoint union of \(I_0\) and the sets \(E_{G}[C]\), for \(C \in \mathcal{C}\), and likewise for \(J\) and \(H\). So
We compare the two sums term by term. Every edge \(e\) of \(J \setminus I\) lies inside \(C_e\). So every edge of \(J_0\) is an edge of \(I\), and \(J_0 \subseteq I_0\). Let \(C \in \mathcal{C}\). Since \(C\) is tight in \(G\), we have \(|E_{G}[C]| + \ell = k\, |C|\), and in particular \(\ell \le k\, |C|\). So the sparsity of \(H\) at \(C\) gives
Summing, we get \(|J| \le |I|\), which contradicts \(|I| {\lt} |J|\).
11.2 The matroid
The \((k, \ell )\)-sparse subsets of \(E(K_V)\) satisfy the independence axioms of a matroid. The empty set is \((k, \ell )\)-sparse, since no set of vertices spans an edge of the graph on \(V\) with no edges (lemma 2.3). A subset of a \((k, \ell )\)-sparse set is \((k, \ell )\)-sparse (lemma 3.5). The augmentation property is lemma 11.6.
Let \(V\) be finite, and let \(k\) and \(\ell \) be non-negative integers with \(\ell {\lt} 2k\). The \((k, \ell )\)-count matroid on \(V\) is the matroid on \(E(K_V)\) whose independent sets are the sets \(I \subseteq E(K_V)\) for which the graph on \(V\) with edge set \(I\) is \((k, \ell )\)-sparse.
Formally, the count matroid is a matroid on the set of all unordered pairs of elements of \(V\), the pairs \(\{ v, v\} \) included, with ground set \(E(K_V)\). So a set of pairs is independent only if it is contained in \(E(K_V)\).
Let \(V\) be finite, let \(k\) and \(\ell \) be non-negative integers with \(\ell {\lt} 2k\), and let \(I\) be a set of unordered pairs of elements of \(V\). Then \(I\) is independent in the \((k, \ell )\)-count matroid on \(V\) if and only if \(I \subseteq E(K_V)\) and the graph on \(V\) with edge set \(I\) is \((k, \ell )\)-sparse.
The independent sets of the count matroid are defined to be these sets (definition 11.7).