3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – David Roberson Mar 8 at 11:29
  • $\begingroup$ @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) $\endgroup$ – Minkov Mar 9 at 7:55
  • $\begingroup$ 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$. $\endgroup$ – David Roberson Mar 9 at 20:37
  • 1
    $\begingroup$ @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. $\endgroup$ – Minkov Mar 11 at 6:45
  • $\begingroup$ BTW, although it is clearly not the same question, you might be interested in Ziv, Koytcheff, Middendorf, and Wiggins. $\endgroup$ – Joshua Grochow Mar 11 at 7:53
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.