Representation of Subgraph Counts using Polynomial of Adjacency Matrix

Question

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.

Answer 1

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.