Subset Powers of Graphs
A possible way to extend the idea of matchings?
Johann Pfaff was a German mathematician of the late 18th and early 19th century. He is best known for the fact that the determinant of a skew-symmetric matrix (that is, where the transpose equals ) is the square of a polynomial in its entries. Actually it is thought that he did not discover this result. Arthur Cayley named the polynomial after Pfaff posthumously in 1852, having published the result in 1847, while was re-discovered and published by Thomas Muir in 1882. At least the polynomial was not named for Carl Gauss. Perhaps this was because Gauss was Pfaff’s student.
Today Ken and I want to talk about a kind of graph powering that may be new, and that may relate in some cases to Pfaffians.
The Pfaffian of a skew-symmetric matrix of odd dimension is always zero. For even dimension it is defined by the formula
Note that for any matrix , is also skew symmetric, so it has a Pfaffian given by the identity
Hence one can do “Pfaffian elimination” where represents doing an elementary operation to the rows, so long as you do the same operation to the columns—which is represented by . This simplifies the computation like with Gaussian elimination, though of course one can also get a polynomial time algorithm for by doing and taking the square root.
The main use of Pfaffians in complexity theory is that the task of counting perfect matchings in a graph sometimes reduces to computing a Pfaffian. When is the adjacency matrix of an undirected -vertex graph, this is already hinted by the above formula: a term of the product is non-zero if and only if the entries involved define a matching. If one can negate half the entries in so that all the terms have the same sign, then the Pfaffian computes the number of perfect matchings. Michael Fisher, Pieter Kasteleyn, and Harold Temperley proved that this was both possible and efficiently computable for planar graphs. My Tech colleague Robin Thomas has a nice survey on graphs and Pfaffians.
Products and Powers
One of the central ideas in mathematics is taking two mathematical objects and and creating a new object that is the “product” of the two. There are more types of products in math than almost any other construct. The root of all products is probably the simple Cartesian product of two sets: . Recall this is the set of all ordered pairs where is in and is in .
Another central idea is taking just one mathematical object and creating a new object that is a “power” of . Usually this is defined in terms of a product by making , or , and so on. The “so on” can include negative and even fractional powers, but always the notion of “power” seems to depend on a notion of “product.” The question is, must it always?
I got into this by considering finite directed graphs that consist only of directed cycles: we will call them cycle graphs. Of course cycle graphs are essentially the graphs that correspond to permutations, and indeed this connection is essential. For now let’s think of them as just graphs. We use to denote that there is an edge from the vertex to vertex , and will drop the subscript when it is clear which graph is. Ken and I started thinking about cycle graphs a long time ago, see this.
For a set let be the sets with each in and the elements all distinct. The notation suggests the number of such subsets, but suppresses “” which is just the size of .
Definition 1 Suppose that is a directed graph and is an integer. Define as the graph with vertices and with an edge from to if and only if for each , there is an edge from to . Call it the subset power.
A first point is that since the nodes of are sets, we are free to permute the elements any way we wish. Consider . There is an edge from to in provided and or and .
A second point is that not all of need be distinct—in the former case we can have or , in the latter or . That is, if is a path in , then in .
If is bipartite, with edges , then for any , has a fairly simple description. If and are subsets of the same size , then is an edge in if and only if has a perfect matching as a subgraph of . But also we can get edges in where and “cross the partition.” That is, if you take any perfect matching of and swap the vertices on the ends of any edge between and , you get such a . You can define exactly such edges in by making such swaps, and when the perfect matching of is unique, these are the only edges one can make from subsets of . However, when it is not unique this process may lead to some double-counting of edges of .
Thus counting is tricky in even when is bipartite, and tricky even in again because of possible double-counting of pairs of edges when are all distinct. But it may be possible in certain cases, and tell us things about counting perfect matchings of subgraphs. We consider simple cases, and find that things are already complex, however.
Why Are Things Complex?
The basic issue is that the subset power of a single cycle can be complex. For example consider the cycle , which has length by our convention. What is —the square of by the direct product? It is easy to see that it consists of vertices and has six cycles all of the same length six. Easy.
Now switch to ask, what is —the square of by the subset product? A natural conjecture seems to be that the subset power also has all cycles of the same length. This is not true. By definition contains
vertices. Right away we see that is not a multiple of so they cannot all have length six. Let be
Then the cycles of are:
Thus has two cycles of length and one of length .
This may be surprising to you. Things can get messier when the subset power is higher. So the analysis of the structure of subset powers can be a challenging task.
Squaring the Cycle
We need to understand the structure of when is a single cycle and . We prove that when equals the issue we saw for 6-cycles is the only one that arises, but it is already tricky.
- If is odd then has cycles all of length .
- If is even then has cycles all of length and one cycle of length .
Proof: The case when is odd is eay so let’s suppose that the length is even. It is convenient to assume that has vertices and edges are modulo . Then a cycle of length will look like
where . Also note that has vertices. It is not hard to prove that
This implies that is a multiple of : thus, is either or is . We will call former the regular case and the later case the short case.
We claim that there is exactly one short cycle of length and all the rest are length . This will imply (2) since
So it remains to show that there is only one short cycle. Let be a vertex on a short cycle. Then which implies that and . Thus the vertex is
Let and be on short cycles. Clearly for any is also on the same cycle: that is
is on the same cycle. Set . Then is on the same cycle: so there is only one short cycle.
Let’s check the example from the last section. Recall we showed that had two cycles of length and one of length . The above Proposition~2 shows that there are cycles of length and one of length : this is exactly what we showed.
There are two main open questions. Consider : the subset power of a single cycle of even length . We wish to count the number of even cycles of . What is a formula for this number? Also even without an explicit formula can we prove that the number for fixed is periodic in the length ? The latter if the period was explicit would allow us to calculate answers. Both these conjectures are non-trivial—I believe—because of the shortcut issue that arises.
Might the concept help with matchings, or ideas of integer-valued flows in parts of a graph? What do you think?