Subset Powers of Graphs

April 18, 2013

tags: complexity, cycles, graphs, Pfaffians, powers, products

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 ${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?

6 Comments leave one →

Bruno Salvy permalink

April 19, 2013 6:21 am

This was a nice post that made me want to play with the first question.
I’ve written Maple code that produces conjectures on what these $C_\ell^{(d)}$ are for the first values of d.
Here are the results (they are only conjectures, but from the look of them, might not be hard to prove, and it is even likely that one can conjecture a general pattern.

The format is : d, \ell, polynomial in \ell meaning that the coefficient of x^i is the number of cycles of length i. The first two lines correspond to your Prop. 2.

2, 2*n+1, x^(2*n+1)*n

2, 2+2*n, x^(n+1)+x^(2+2*n)*n

3, 3*n+1, ((1/2)*(-1)^(n+1)+1/2)*x^(1/2+(3/2)*n)+((3/2)*n-1/4+(1/4)*(-1)^n)*x^(3*n+1)

3, 3*n+2, -(1/2)*((-1)^(n+1)-1)*x*x^((3/2)*n)-(1/4)*((-1)^n-6*n-1)*x*x^(3*n+1)

3, 3+3*n, (3/4+(1/4)*(-1)^n+(3/2)*n)*x^(3+3*n)+((1/2)*(-1)^(n+1)+1/2)*x^((3/2)*n+3/2)

4, 4*n+1, 2*x^(4*n+1)*n

4, 4*n+2, 2*x*x^(4*n+1)*n+x*x^(2*n)

4, 4*n+3, x^(4*n+3)*(2*n+1)

4, 4+4*n, (2*n+1)*x^(4+4*n)+x^(2*n+2)

5, 1+5*n, (-1/4+(1/4)*(-1)^n+(5/2)*n)*x^(1+5*n)+((1/2)*(-1)^(n+1)+1/2)*x^(1/2+(5/2)*n)

5, 5*n+2, -(1/2)*((-1)^(n+1)-1)*x*x^((5/2)*n)-(1/4)*((-1)^n-10*n-1)*x*x^(1+5*n)

5, 3+5*n, (3/4+(1/4)*(-1)^n+(5/2)*n)*x^(3+5*n)+((1/2)*(-1)^(n+1)+1/2)*x^(3/2+(5/2)*n)

5, 5*n+4, (-(1/2)*(-1)^(n+1)+1/2)*x^2*x^((5/2)*n)+(-(1/4)*(-1)^n+(5/2)*n+5/4)*x^2*x^(5*n+2)

5, 5+5*n, (7/4+(1/4)*(-1)^n+(5/2)*n)*x^(5+5*n)+((1/2)*(-1)^(n+1)+1/2)*x^((5/2)*n+5/2)

6, 6*n+1, 3*x^(6*n+1)*n

6, 6*n+2, 3*x*x^(6*n+1)*n+x*x^(3*n)

6, 6*n+3, x^(6*n+3)*(3*n+1)

6, 4+6*n, (3*n+1)*x^(4+6*n)+x^(3*n+2)

6, 6*n+5, x^(6*n+5)*(3*n+2)

6, 6+6*n, (3*n+2)*x^(6+6*n)+x^(3*n+3)

Hope this helps,

Bruno.
P.-S. I can email you the maple session if you’re interested.

Loading...

Reply
Leonid Gurvits permalink

April 19, 2013 11:47 am

Nice post! It looks like your construction is the permanent analogue of the matrix outer power:, i.e. the matrix { A(X,Y) =: det(A_{X,Y})} ,where A_{X,Y} is a submatrix with rows from X
and columns from Y. The standard outer d-power is nice for its eigen-values are easily expressed in terms of eigen-values of A: they are just all d-products of eigenvalues
with distinct “numbers”.
Anyway, if A corresponds to a cycle, then
the difference between your power and the standard outer power is only in some signs
of non-zero entries. Perhaps this observation is sufficient to compute the cycle structure
of your graph.

Loading...

Reply
Daniel Pragel permalink

April 25, 2013 5:09 pm

I am intrigued; I had not heard of this sort of construction before. Let n(l,d,k) be the number of directed cycles of length k in the graph C_l^(d), where C_l is a directed cycle of length l. I believe that I can show that n(l,d,k) = n(k,dk/l, k). Basically, we can look at blocks of vertices of C_l and treat them as a single vertex of C_k.

In order to have a cycle of length k in C_l^(d), if one of the vertices of C_l^(d) in this cycle contains a, it must also contain a + k, a + 2k, a + 3k,… a + (m-1)k, where m = l/k. Thus, we can treat this collection of vertices of C_l as a single entity, and we have reduced the problem considerably.

Please contact me by email if you would like to discuss this matter further; I may be completely wrong, but I think the general problem is very solvable.

Loading...

Reply
Daniel Pragel permalink

April 26, 2013 1:40 pm

To follow up on my previous comment, I believe that I have an explicit formula for n(l,d,k), using an inclusion-exclusion argument. It is zero unless k divides l and l divides dk. Otherwise, let c = dk/l and let

p_1^n_1*p_2^n_2… p_m^n_m

be the prime factorization of the greatest common divisor of k and c. If we consider any subset S of {1,2,…,m}, and we let P_S be the product of p_i for all i in S, then n(l,d,k) is equal to the sum over all possible S of the following terms:

(-1)^|S|*[(k/P_S – 1) Choose (c/P_S – 1)]

divided by the quantity (c – 1).

I am working on writing up my results in LaTex, so email me if you would like me to send you a copy when I finish. This is very preliminary, so there is a good chance there is a mistake somewhere in my work, but I wanted to share my progress in the hopes that it would be helpful.

Loading...

Reply
Daniel Pragel permalink

May 13, 2013 9:30 pm

For what it is worth, I have posted my results to the arXiv here:

http://arxiv.org/abs/1305.2543

I believe that I have found a formula that computes the number of cycles of a given length in C_l^(d), and I describe that formula in my paper.

Loading...

Reply
- KWRegan permalink
  
  May 14, 2013 10:43 pm
  
  Thank you very much. With this and the above, I hope others take notice, and we will take better notice when we can.
  
  Loading...
  
  Reply

	Frank Vega on P=NP and Bitcoin
	Frank Vega on P=NP and Bitcoin
	Frank Vega on P=NP and Bitcoin
	Wayne Shanks on Biblical Codes
	Frank Vega on P=NP and Bitcoin
	Frank Vega on P=NP and Bitcoin
	Frank Vega on Limits On Matrix Multiplicatio…
	Frank Vega on P=NP and Bitcoin
	Frank Vega on P=NP and Bitcoin
	Frank Vega on Limits On Matrix Multiplicatio…
	Frank Vega on P=NP and Bitcoin
	Frank Vega on P=NP and Bitcoin
	Frank Vega on P=NP and Bitcoin
	Frank Vega on P=NP and Bitcoin
	Héctor Corvalán on Novel Proofs of the Infinitude…

a personal view of the theory of computation

Subset Powers of Graphs

Products and Powers

Cycle Graphs

Subset Power

Why Are Things Complex?

Squaring the Cycle

Open Problems

Like this:

Related

Leave a Reply to Bruno SalvyCancel reply

Subscribe to Gödel’s Lost Letter

Our Book

Recent Posts

Top Posts

Recent Comments

Blogroll

Archives

Sitemeter

a personal view of the theory of computation

Subset Powers of Graphs

Products and Powers

Cycle Graphs

Subset Power

Why Are Things Complex?

Squaring the Cycle

Open Problems

Share this:

Like this:

Related

Leave a Reply to Bruno SalvyCancel reply

Subscribe to Gödel’s Lost Letter

Our Book

Recent Posts

Top Posts

Recent Comments

Blogroll

Archives

Sitemeter

Discover more from Gödel's Lost Letter and P=NP