3
$\begingroup$

Fix any $k \geq 3$, and suppose I have a simple undirected graph $G=(V,E)$. I want a bound on the number of $k$ cycles in $G$ as a function of $|E|$. In particular, I would like to prove the following "conjectured" statement:

W.T.S: Given any $G=(V,E)$, the number of $k$-cycles in $G$ is at most $O(|E|^{k/2})$.

Clearly $\binom{|V|}{k}$ is tight if we only wanted a bound in terms of $|V|$, which comes from the complete graph on $|V|$ vertices. However, it is not as clear how to prove a tight upper bound in terms of $|E|$. The intuition for the conjecture is that, up to a constant, it seems that it should be optimal to arrange your edges in a complete graph (if $k$ is even, you do win a constant by taking a complete bipartite graph instead of a complete graph).

There seem to be a few proofs of this fact for triangles (k=3), for instance https://math.stackexchange.com/questions/823481/number-of-triangles-in-a-graph-based-on-number-of-edges. However, they don't generalize in any clear way to larger $k$. Moreover, I don't know of any k-cycle enumeration algorithms for k>3 that are parameterized by $|E|$ (the runtime of which would provide an upper bound).

For my application I actually only need bounds for odd $k$, but it seems that any such proof should generalize to any $k$. Also, to be clear, I'm only interested in asymtotic bounds here in terms of $|E|$ (getting tight constants seem much more difficult). Any suggestions or references that I missed would be much appreciated.

$\endgroup$
  • 1
    $\begingroup$ For $k=4$ the appropriate complete graph has nearly twice as many $k$-cycles as the complete bipartite graph, not that that changes things. For example $K_{50}$ and $K_{35,35}$ and each have $|E|=1225$ but the first has $690900$ $4$-cycles and the latter has $354025.$ The same should be true for larger ever $k$ as well. $\endgroup$ – Aaron Meyerowitz Jan 30 at 4:59
  • $\begingroup$ Ooops, right you are. I miscounted the number of 4 cycles in the complete graph, I forgot that four vertices give rise to multiple 4-cycles. Thanks for catching this! $\endgroup$ – Rajesh Jayaram Jan 31 at 17:48
5
$\begingroup$

Yes, this is addressed in the paper:

Rivin, Igor, Counting cycles and finite dimensional (L^{p}) norms, Adv. Appl. Math. 29, No. 4, 647-662 (2002). ZBL1013.05042.

$\endgroup$
  • 1
    $\begingroup$ Incredible -- I had a feeling that bounding Tr(A^k) would be a good approach, but I didn't see how to do it. The fact that Tr(A^2) = |E| is a great catch. Thanks for the beautiful proof! $\endgroup$ – Rajesh Jayaram Jan 30 at 2:08
  • $\begingroup$ @RajeshJayaram Thanks for the kind words! $\endgroup$ – Igor Rivin Jan 30 at 2:50

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.