Subset Powers of Graphs

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 ${A}$ (that is, where the transpose ${A^T}$ equals ${-A}$ ) is the square of a polynomial ${\text{pf}(A)}$ 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 ${\det(A) = \text{pf}(A)^2}$ 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 ${2n}$ it is defined by the formula

$\displaystyle \text{pf}(A) = \frac{1}{n!2^n}\sum_{\sigma \in S_{2n}}(-1)^{sgn(\sigma)}\prod_{i=1}^n A(\sigma(2i-1),\sigma(2i)).$

Note that for any matrix ${B}$ , ${BAB^T}$ is also skew symmetric, so it has a Pfaffian given by the identity

$\displaystyle \text{pf}(BAB^T) = \det(B)\text{pf}(A).$

Hence one can do “Pfaffian elimination” where ${B}$ represents doing an elementary operation to the rows, so long as you do the same operation to the columns—which is represented by ${B^T}$ . This simplifies the computation like with Gaussian elimination, though of course one can also get a polynomial time algorithm for ${\text{pf}(A)}$ by doing ${\det(A)}$ 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 ${A}$ is the adjacency matrix of an undirected ${2n}$ -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 ${A}$ 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 ${A}$ and ${B}$ and creating a new object ${C}$ 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: ${A \times B}$ . Recall this is the set of all ordered pairs ${(a,b)}$ where ${a}$ is in ${A}$ and ${b}$ is in ${B}$ .

Another central idea is taking just one mathematical object ${A}$ and creating a new object ${C}$ that is a “power” of ${A}$ . Usually this is defined in terms of a product ${\times}$ by making ${C = A \times A}$ , or ${C = A \times A \times A}$ , 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?

Cycle Graphs

I got into this by considering finite directed graphs ${G=(V,E)}$ 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 ${x \rightarrow_{G} y}$ to denote that there is an edge from the vertex ${x}$ to vertex ${y}$ , and will drop the subscript when it is clear which graph ${G}$ is. Ken and I started thinking about cycle graphs a long time ago, see this.

Subset Power

For a set ${A}$ let ${A^{(d)}}$ be the sets ${\{x_{1},\dots,x_{d}\}}$ with each ${x_{i}}$ in ${A}$ and the elements ${x_{1},\dots,x_{d}}$ all distinct. The notation suggests the number ${\binom{n}{d}}$ of such subsets, but suppresses “ ${n}$ ” which is just the size of ${A}$ .

Definition 1 Suppose that ${G}$ is a directed graph and ${d \ge 1}$ is an integer. Define ${G^{(d)}}$ as the graph with vertices ${V(G)^{(d)}}$ and with an edge from ${\{x_{1},\dots,x_{d}\}}$ to ${\{y_{1},\dots,y_{d}\}}$ if and only if for each ${i}$ , there is an edge from ${x_{i}}$ to ${y_{i}}$ . Call it the subset power.

A first point is that since the nodes of ${G^{(d)}}$ are sets, we are free to permute the elements ${y_{i}}$ any way we wish. Consider ${H = G^{(2)}}$ . There is an edge from ${\{x,y\}}$ to ${\{u,v\}}$ in ${H}$ provided ${x \rightarrow_{G} u}$ and ${y \rightarrow_{G} v}$ or ${x \rightarrow_{G} v}$ and ${y \rightarrow_{G} u}$ .

A second point is that not all of ${u,v,x,y}$ need be distinct—in the former case we can have ${x = v}$ or ${y = u}$ , in the latter ${x = u}$ or ${y = v}$ . That is, if ${a \rightarrow b \rightarrow c}$ is a path in ${G}$ , then ${\{a,b\} \rightarrow \{b,c\}}$ in ${G^{(2)}}$ .

If ${G}$ is bipartite, with edges ${E(G) \subseteq A \times B}$ , then for any ${d}$ , ${G^{(d)}}$ has a fairly simple description. If ${A' \subseteq A}$ and ${B' \subseteq B}$ are subsets of the same size ${d}$ , then ${(A',B')}$ is an edge in ${G^{(d)}}$ if and only if ${(A',B')}$ has a perfect matching as a subgraph of ${G}$ . But also we can get edges ${(C,D)}$ in ${G^{(d)}}$ where ${C}$ and ${D}$ “cross the partition.” That is, if you take any perfect matching of ${(A',B')}$ and swap the vertices on the ends of any edge between ${A'}$ and ${B'}$ , you get such a ${(C,D)}$ . You can define exactly ${2^d}$ such edges in ${G^{(2)}}$ by making such swaps, and when the perfect matching of ${(A',B')}$ is unique, these are the only edges one can make from subsets of ${A' \cup B'}$ . However, when it is not unique this process may lead to some double-counting of edges of ${G^{(d)}}$ .

Thus counting is tricky in ${G^{(d)}}$ even when ${G}$ is bipartite, and tricky even in ${G^{(2)}}$ again because of possible double-counting of pairs of edges when ${u,v,x,y}$ 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 ${C_{6}}$ , which has length ${6}$ by our convention. What is ${H = C_{6}^{2} = G \times G}$ —the square of ${G}$ by the direct product? It is easy to see that it consists of ${36}$ vertices and has six cycles all of the same length six. Easy.

Now switch to ask, what is ${H = C_{6}^{(2)}}$ —the square of ${G}$ 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 ${H}$ contains

$\displaystyle {6 \choose 2} = 15$

vertices. Right away we see that ${15}$ is not a multiple of ${6}$ so they cannot all have length six. Let ${C_{6}}$ be

$\displaystyle 1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow 6 \rightarrow 1.$

Then the cycles of ${H}$ are:

$\displaystyle \begin{array}{rcl} \{1,2\} \rightarrow \{2,3\} \rightarrow \{3,4\} \rightarrow \{4,5\} \rightarrow \{5,6\} \rightarrow \{6,1\} \rightarrow \{1,2\}, \\ \{1,3\} \rightarrow \{2,4\} \rightarrow \{3,5\} \rightarrow \{4,6\} \rightarrow \{5,1\} \rightarrow \{6,2\} \rightarrow \{1,3\}, \\ \{1,4\} \rightarrow \{2,5\} \rightarrow \{3,6\} \rightarrow \{4,1\}. \end{array}$

Thus ${H}$ has two cycles of length ${6}$ and one of length ${3}$ .

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 ${C^{(d)}}$ when ${C}$ is a single cycle and ${d \geq 2}$ . We prove that when ${d}$ equals ${2}$ the issue we saw for 6-cycles is the only one that arises, but it is already tricky.

Proposition 2 Let ${H = C^{(2)}}$ where ${C}$ is a cycle of length ${\ell}$ . Then

If ${\ell}$ is odd then ${H}$ has ${(\ell-1)/2}$ cycles all of length ${\ell}$ .
If ${\ell}$ is even then ${H}$ has ${\ell/2-1}$ cycles all of length ${\ell}$ and one cycle of length ${\ell/2}$ .

Proof: The case when ${\ell}$ is odd is eay so let’s suppose that the length ${\ell}$ is even. It is convenient to assume that ${C}$ has vertices ${0,1,\dots,\ell-1}$ and edges are modulo ${\ell}$ . Then a cycle of length ${q}$ will look like

$\displaystyle \{x,y\} \rightarrow \cdots \rightarrow \{x+q-1,y+q-1\} \rightarrow \{x+q,y+q\},$

where ${ \{x+q,y+q\} = \{x,y\} }$ . Also note that ${H}$ has ${{\ell \choose 2}}$ vertices. It is not hard to prove that

$\displaystyle 2 \cdot q \equiv 0 \bmod \ell.$

This implies that ${q}$ is a multiple of ${\ell/2}$ : thus, ${q}$ is either ${\ell}$ or is ${\ell/2}$ . 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 ${\ell/2}$ and all the rest are length ${\ell}$ . This will imply (2) since

$\displaystyle \left({\ell \choose 2}-\ell/2 \right)/\ell = \ell/2-1.$

So it remains to show that there is only one short cycle. Let ${\{x,y\}}$ be a vertex on a short cycle. Then ${q \circ \{x,y\} = \{x+q,y+q\}}$ which implies that ${x +q = y}$ and ${y + q = x}$ . Thus the vertex is

$\displaystyle \{x, x+q\}.$

Let ${\{x,x+q\}}$ and ${\{u,u+q\}}$ be on short cycles. Clearly ${k \circ \{x,x+q\}}$ for any ${k}$ is also on the same cycle: that is

$\displaystyle \{x+k,x+k+q\}$

is on the same cycle. Set ${k = u-x}$ . Then ${ \{x+k,x+k+q\} = \{u,u+q\}}$ is on the same cycle: so there is only one short cycle. $\Box$

Let’s check the example from the last section. Recall we showed that ${C_{6}^{(2)}}$ had two cycles of length ${6}$ and one of length ${3}$ . The above Proposition~2 shows that there are ${\frac{6}{2}-1}$ cycles of length ${6}$ and one of length ${\frac{6}{2}}$ : this is exactly what we showed.

Open Problems

There are two main open questions. Consider ${G = C_{\ell}^{(d)}}$ : the subset power of a single cycle of even length ${\ell}$ . We wish to count the number of even cycles of ${G}$ . What is a formula for this number? Also even without an explicit formula can we prove that the number for fixed ${d}$ is periodic in the length ${\ell}$ ? 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?