Suppose that $G$ is a simple, undirected graph with $n$ vertices and $m$ edges. Conjecture: The total number of vertex paths of length $l$ is at most $$ n (2 m/n)^{l-1} $$

The heuristic basis for this is that the average degree is $2 m/n$, and this is the total number of ways of choosing paths $l$ vertices in such a graph.

Is this conjecture true? Is there another bound known on the number of such paths?

  • 2
    $\begingroup$ It fails for stars. $\endgroup$ Jan 14 '16 at 19:01
  • $\begingroup$ Your paths are simple? $\endgroup$ Jan 15 '16 at 1:23
  • $\begingroup$ It seems more reasonable if you say "at least" instead of "at most" since the Perron-Frobenius eigenvectors tend to have a higher weight on high degree vertices. $\endgroup$ Jan 15 '16 at 5:01

Suppose the graph is connected. Let $\mu$ be the eigenvalue of the adjacency matrix $A$ with the largest magnitude. This is positive and real by the Perron-Frobenius theorem. The number of (not necessarily simple) paths of length $l$ is asymptotic to a polynomial times $\mu^l$. The Rayleigh quotient characterization of the largest eigenvalue says that

$$\mu = \max_v \frac{v^T A v}{v^T v} \ge \frac{\vec{1}^T A \vec{1}}{\vec{1}^T\vec{1}} = \frac{2 ~\# \textrm{edges}}{n} = \frac{2m}{n}$$

where $\vec{1}$ is the all-$1$ vector. You only get equality when the uniform distribution is a principal eigenvector, which means that all vertices have the same degree. Otherwise, the conjecture fails for sufficiently large path lengths $l$ since the conjectured bound is asymptotically smaller than $\mu^l$.


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.