My paper with Vijay Vazirani on parallel matching (soon to appear in SPAA) is based on the idea of a “matching-mimicking network”. If \(G\) is a graph with a designated set \(T\) of terminal vertices, then a matching-mimicking network for \((G,T)\) is another graph \(H\) with the same terminals that has the same pattern of matchings. Here, by a pattern of matchings, I mean a family of subsets of \(T\), the subsets that can be covered by a matching that also covers all non-terminal vertices. We included a messy case analysis that, after some simplifications due to symmetry, had 21 cases for the matching mimicking networks on at most three terminals.

By now, I think I understand patterns of matchings a lot better, enough to do the three-terminal case in only four cases and to extend the analysis to four terminals in only seven more cases. The starting point is the observation that these patterns of matchings are even Δ-matroids.

One way to think of a Δ-matroid is that it’s just a convex polyhedron or polytope in Euclidean space of some dimension \(d\), with the properties that all vertex coordinates are \(0\) or \(1\) and all edge lengths are \(1\) or \(\sqrt{2}\). An even Δ-matroid has the stronger property that all edge lengths are \(\sqrt{2}\), as is true for the three-dimensional regular tetrahedron with vertex coordinates (written in a more compact form as bitvectors) \(000\), \(011\), \(101\), and \(110\).

Regular tetrahedron formed from alternating vertices of a cube

Alternatively one can consider the same kind of structure to be a family of sets, drawn from a universe of \(d\) elements that correspond to the dimensions of the space. Each set in the family corresponds to a vertex of the polytope and includes the elements whose coordinates are one. So over the three-element set \(\{a,b,c\}\) the same regular tetrahedron can be written as the family of sets

\[\bigl\{ \emptyset, \{b,c\}, \{a,c\}, \{a,b\} \bigr\}.\]

When expressed in this way, the sets of a Δ-matroid obey an exchange axiom: if two sets \(X\) and \(Y\) differ on whether they include some element \(a\), then there must exist an element \(b\) on which they also differ, so that the symmetric difference of sets \(X\triangle\{a,b\}\) also belongs to the Δ-matroid. By repeatedly applying this axiom one can connect \(X\) to \(Y\) by a geodesic path (in Hamming distance) of two-element moves. For the bases of a matroid, we have a stronger requirement that one of the two elements belongs to \(X\) and the other belongs to \(Y\), or equivalently that all sets have the same size, but a Δ-matroid relaxes this requirement. It’s not even required that \(a\ne b\)! But in an even Δ-matroid \(a\) and \(b\) must be distinct, because otherwise the step would be along an edge of length one. Another way of expressing the extra requirements of an even Δ-matroid over an arbitrary Δ-matroid is that all sets must have the same parity (all have even size, or all have odd size).

So anyway, back to matching. Suppose that both \(X\) and \(Y\) are sets drawn from a pattern of matchings. Choose arbitrarily a matching representing each set. Then the symmetric difference of these matchings is a collection of disjoint alternating paths and cycles, and we can get from \(X\) to \(Y\) by a sequence of steps in which we take the symmetric difference of the current matching by one of the alternating paths. So this gives us not just one geodesic from \(X\) to \(Y\) but a lot of different geodesics, one for each ordering of the alternating paths. Expressed as an exchange axiom, this means that when two sets \(X\) and \(Y\) differ, the elements on which they differ can be partitioned into pairs, the symmetric differences with which can be performed independently. You can pick any subset of the pairs of differing elements, and change each of those pairs, leaving the rest alone. Because this is a strengthening of the even Δ-matroid axiom, every matching pattern is an even Δ-matroid.

Expressed in polyhedral terms, this stronger exchange axiom means that every two vertices at distance \(\sqrt{2k}\) from each other are connected by a \(k\)-dimensional hypercube with side length \(\sqrt 2\). This is a little weird, because we started with a hypercube but then eliminated half of its vertices (by the parity condition) to get something else. Now we have hypercubes again, of lower dimension. They must be tilted with respect to the coordinate axes: each axis of one of these lower-dimensional hypercubes is tilted at a 45 degree angle with respect to the coordinate system of the overall polytope.

Not every even Δ-matroid obeys this sub-hypercube property. On the other hand, I was expecting the matching patterns that are matroids (all sets are the same size) to be transversal matroids (maximal subsets of vertices on one side of a bipartite graph that can be covered by a matching), and they aren’t. There is a six-element non-transversal matroid, whose six elements are the edges of a triangle with doubled edges and whose sets are pairs of edges from different sides of the triangle. But it is the pattern of matchings of a tree in which the (non-terminal) root has three children, each of which has two terminals as its children.

Conveniently, whether a 0-1 polyhedron can be represented by a pattern of matchings depends only on its shape and not on its orientation. You can obviously permute the coordinates of a polyhedron that represents a pattern of matchings, by relabeling which coordinate corresponds to which terminal vertex. But you can also reflect the polyhedron across any one of its coordinates by modifying the graph whose matchings represent it in the following way: turn the terminal vertex for that coordinate into a non-terminal, and attach a new degree-one terminal vertex to it. These permutations and reflections generate all the symmetries of the hypercube in which the 0-1 polyhedron lives. So to find small matching-mimicking networks, we only need to look at one representative 0-1 polyhedron in each symmetry class. If we find a small network for this representative, we can modify it to create a different small matching-mimicking network for every other 0-1 polyhedron with the same shape.

So what are the possible shapes? Let’s define the dimension of a Δ-matroid to be the number of coordinates of the polytope that take both values, \(0\) and \(1\), at different vertices. Then a 0-dimensional even Δ-matroid must be a single point (\(K_1\)), there are no 1-dimensional even Δ-matroids, and a two-dimensional even Δ-matroid must be a line segment (\(K_2\)). There are two three-dimensional even Δ-matroids: a triangle \(K_3\) and the tetrahedron shown above, \(K_4\). The cube exchange axiom for patterns of matching starts to kick in for four-dimensional even Δ-matroids, whose vertices must be subsets of the four-dimensional hyperoctahedron \(K_{2,2,2,2}\). (This is the shape formed from a four-dimensional hypercube by keeping only vertices with the same parity as each other, just as we formed a regular tetrahedron by doing the same thing to a three-dimensional cube.) Here’s a drawing of \(K_{2,2,2,2}\) from an earlier post:

The hyperoctahedral graph K_{2,2,2,2}

If there are no two opposite vertices, we get \(K_{1,1,1,1}\) (a regular tetrahedron, again, but embedded in a four-dimensional way into the hypercube). Otherwise, we must take at least two pairs of opposite vertices to form a square, and the cases are \(K_{2,2}\) (only the square), \(K_{2,2,1}\) (a square pyramid), \(K_{2,2,2}\) (an octahedron), \(K_{2,2,1,1}\), \(K_{2,2,2,1}\) (an octahedral pyramid), and \(K_{2,2,2,2}\) (the hyperoctahedron). All of these polyhedra can be represented as matching-mimicking networks with the additional property that all vertices are terminals:

Matching-mimicking networks for up to four terminals

Based on these small examples, it’s tempting to guess that when a pattern of matchings includes the empty set, the whole pattern is just the set of matchings on a graph whose edges are the pairs of terminals in the pattern. But it isn’t true. The square pyramid \(K_{2,2,1}\), for instance, can represent the pattern of matchings

\[\bigl\{\emptyset, \{ab\}, \{bc\}, \{cd\}, \{ad\} \bigr\},\]

with the empty set at the apex of the pyramid. In this pattern, even though one can match terminal pairs \(a\)—\(b\) or \(c\)—\(d\), one can’t take the union of those two matchings and cover all four terminals. (This is what you get by reflecting the two middle terminals of the network shown above for \(K_{2,2,1}\); its matching-mimicking network is a tree with two interior non-terminals and four terminal leaves.) My guess is that the number of patterns of matching should grow quickly relative to the number of graphs, so for large enough numbers of terminals it should not be possible to use graphs without non-terminals or their complements. But I haven’t taken the case analysis far enough to find an example of this.

(Discuss on Mastodon)