1
$\begingroup$

My (philosophical) question arises from reading the wonderful paper of Chung-Graham-Wilson where the authors introduces the notion of quasi-random graphs.

The main purpose of the paper is to show that many properties of a graph are in fact equivalent. I focus in this question in two properties, namely (I will use the notation of the paper):

enter image description here

P3 property gives information concering the second largest eigenvalue of the adjacency matrix of the graph G

enter image description here

where $N_G(C_t)$ is the number of copies of the cycle on t vertices. The paper shows that, among several other properties, G satisfies $P_2(4)$ (See that t=4 here) if and only if G satisfies $P_3$.

In order to prove that $P_2(4)$ implies $P_3$ one can use the following easy property: the number of 4-cycles in G can be obtained by estimating

$$\sum_{i=1}^{n}\lambda_i^4,$$

which is, up to lower order terms, the number of 4-cycles. Hence, having upper bounds from this sum would give upper bounds on the second largest element in the sum.

In the paper the proof that $P_3$ implies $P_2(4)$ is not direct, and uses at least 5 intermediate implications. So my question is the following:

Is there a direct way to bound the number of 4-cycles directly and just using spectral information on the graph (namely, about the second largest eigenvalue, or even its multiplicity)?

It seems to me that something could be said here, even more because we have a direct and easy relation between the number of 4-cycles and the spectrum of the matrix.

$\endgroup$
  • 2
    $\begingroup$ $\sum_i \lambda_i^4$ is not the number of 4-cycles. It is the number of closed walks of length 4. For example, it is positive for a tree, which has no 4-cycles. $\endgroup$ – Brendan McKay Apr 27 at 12:28
  • $\begingroup$ completely true: this sum is equal to 4-cycles+o(n^4), and hence, having information on a bound for this gives information on the eigenvalues...the converse I do not know how to do it directly (if possible) $\endgroup$ – gaussian-matter Apr 27 at 14:01

Your Answer

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

Browse other questions tagged or ask your own question.