# Representation of Subgraph Counts using Polynomial of Adjacency Matrix

We consider a graph $$G$$ of size $$d$$ with adjacency matrix $$A$$, whose entries take value in $$\{0,1\}$$. We are interested in the number of a certain connected subgraph $$S$$ of size $$k$$ in $$G$$. For example, the subgraph $$S$$ consists of edges $$(1,2),(2,3),(3,4),(4,2)$$ up to relabeling of the $$k = 4$$ vertices $$1,2,3,4$$. We can also view this subgraph as a path'' of length $k = 4$ from vertex $1$ to vertex $2$. Here we allow repeated vertices in thepath'', for example, vertex $$2$$ appears twice.

Question: Is the following claim true?

Let $$s$$ denote the number of subgraphs $$S$$ in $$G$$. For any graph $$G$$ and subgraph $$S$$, there exist $$\{\Theta^{(i)}\}_{i=1}^k$$, which only depend on the subgraph $$S$$, such that $$s = \sum_{i = 1}^k\langle \Theta^{(i)}, A^i \rangle,$$ where $$\Theta^{(i)} \in \mathbb{R}^{d\times d}$$ is the coefficient of the $$i$$-th order polynomial of the adjacency matrix $$A$$, and $$k$$ is the size of the subgraph of interest.

• It is not completely clear to me what you are asking. What is the freedom in choosing the $\Theta^{(i)}$? If I am allowed to pick them after knowing both $G$ and $S$, then the statement is trivially true: pick $\Theta^{(0)} = (s/d)I$ and all other $\Theta^{(i)}$ equal to zero. But of course they should depend on $S$, and also on $G$ (since at the very least the $\Theta^{(i)}$ should be $d \times d$ matrices, and $d$ depends on $G$). I assume I am just not understanding something though. Perhaps you could clarify? Out of curiosity, what is this related to? – David Roberson Mar 8 at 11:29
• @DavidRoberson Thanks for pointing out. The choice of $\Theta^{(i)}$ will depend on $S$ and $G$. I am trying to prove the existence of such representation. Here the summation starts from $i = 1$, which should rule out the trivial case. I am trying to connect the moment of graphon [1] with the polynomial of adjacency matrix or the number of paths on the graph. ([1] Moments of Two-Variable Functions and the Uniqueness of Graph Limits Christian Borgs, Jennifer Chayes, Laszlo Lovasz) – Minkov Mar 9 at 7:55
• Sorry I mistook the starting index in the sum, though I think it shouldn't make much difference. If $\Theta^{(1)}$ is any matrix such that $\langle \Theta^{(1)},A\rangle \ne 0$, then one can obtain $\langle \Theta^{(1)},A\rangle = s$ by rescaling. So maybe I am still missing something. You say you are interested in the # of paths, but that you allow repeated vertices. Do you also allow repeated edges? If so, then these are usually called walks and the # of walks of length $k$ from vertex $u$ to $v$ is just $(A^k)_{uv}$. So the total # of walks of length $k$ is the sum of the entries of $A^k$. – David Roberson Mar 9 at 20:37
• @DavidRoberson I now see where the confusion is. I meant that for any subgraph $S$, we have a fixed set of $\Theta^{(i)}$, which only depends on $S$, no matter what $G$ is. Here I am not interested in the number of possible walks from $u$ to $v$. Instead I am interested in a specific subgraph that takes the form $\{(1,2), (2,3), (3,4), (4,2)\}$ (up to relabeling of the vertices). (In this example, it is a "triangle plus one edge".) Thanks for the clarification. I have revised the question accordingly. – Minkov Mar 11 at 6:45
• BTW, although it is clearly not the same question, you might be interested in Ziv, Koytcheff, Middendorf, and Wiggins. – Joshua Grochow Mar 11 at 7:53

I am fairly certain this is false in general (although it works for certain special $$S$$ and might work for small values of $$d$$, but when $$d$$ is sufficiently large relative to $$k=|V(S)|$$ it shouldn't work). Here's why, and some reasoning that might help you characterize exactly for which $$S$$ it works.

Fix $$S$$, and let $$s(G)$$ denote the number of copies of $$S$$ in a graph $$G$$ (and similarly $$s(A)$$ where $$A = A(G)$$ is the adjacency matrix). Note that $$s(G)$$ is invariant under isomorphisms of $$G$$, that is $$s(A) = s(\pi A \pi^{-1})$$ for any permutation matrix $$\pi$$. Since the number of $$\{0,1\}$$ matrices is $$2^{d^2}$$ (and even if we disallow self-loops it is still asymptotically the same order of magnitude), this implies that for sufficiently large $$d$$, if $$s(A)$$ is any polynomial in the entries of $$A$$, then $$s$$ is invariant under this action of $$S_d$$. If $$s$$ has the form you ask about in your question, this is the same as saying that each $$\Theta^{(i)}$$ is invariant under conjugation by $$S_d$$. However, because this action of $$S_d$$ is 2-transitive on $$[d] = \{1,...,d\}$$, the only such matrices are $$\alpha I + \beta J$$ where $$I = I_d$$ is the identity matrix and $$J$$ is the all-ones matrix. This means that we can rewrite your summation as

$$\sum_{i=1}^k \langle \alpha_i I + \beta_i J, A^i \rangle = \sum_{i=1}^k \alpha_i tr(A^i) + \beta_i t(A^i),$$

where $$t(X)$$ is the just the sum of all the entries of $$X$$. $$tr(A^i)$$ is simply $$2i$$ times the number of $$i$$-cycles (including "degenerate" $$i$$-cycles that visit the same vertex more than once), and $$t(A^i)$$ is the total number of paths of length $$i$$ (again, including paths that repeat the same vertex more than once).

Examples where it works. There are clearly some $$S$$ for which this works out. For example, if $$S$$ is a single edge, then we have $$s(A) = t(A)$$. If $$S$$ is a path with 2 edges, then $$s(A) = 1/2(t(A^2) - tr(A^2))$$ (here I am counting general subgraphs, not necessarily induced; it wasn't clear to me if you wanted only induced subgraphs or not). If $$S$$ is a triangle, then $$s(A) = tr(A^3) / 6$$.

Towards a counterexample. Here's how to come up with an example where it fails (I expect this to be the general case). For example, consider $$k=4$$; then we are only considering $$A^1, A^2, A^3, A^4$$, and we have

$$tr(A^1) = 0$$ (assuming no self-loops)

$$tr(A^2) = 2e$$ (assuming undirected here, $$e =$$number of edges)

$$tr(A^3) = 6 \cdot \text{(# triangles)}$$

$$tr(A^4) = 8 \cdot \text{(# 4-cycles)} + \sum_v d_v (d_v - 1)$$

$$t(A^1) = e$$

$$t(A^2) - tr(A^2) = 2 \cdot (\# P_3$$) ($$P_3$$ = path on 3 vertices, 2 edges)

$$t(A^3) - tr(A^3) = 2 \cdot (\# P_4) + \sum_v d_v (d_v - 1)$$

$$t(A^4) - tr(A^4) = 2 \cdot (\# P_5) + \sum_v d_v p_v$$, where $$p_v$$ is the number of simple (=nondegenerate) paths of length 2 beginning at $$v$$

From these, it looks like it shouldn't be too hard to show that there is no such representation for counting paths of length 4 (=$$P_5$$). The issue is that in the sum $$\sum_v d_v p_v$$, we are essentially considering the correlation between the degree and the number of paths of length 2 emanating from a given vertex, but none of the other 8 terms let us consider such correlation. If you actually want to prove it fails, I'd start considering various graphs on $$d$$ vertices for small values of $$d$$ (maybe even $$d=5$$ would do it); use these to get inhomogeneous linear equations for the $$\alpha_i,\beta_i$$, and show that the linear system is unsatisfiable.