Let $C_4$ be a cycle with four vertices. For an arbitrary graph $G$ with $n$ vertices and m edges say $m>n\sqrt n$, how many $C_4$s exist? Is there a lower bound for this?
$\begingroup$
$\endgroup$
1
-
3$\begingroup$ Is this a research-level question in theoretical computer science? $\endgroup$– Peter MortensenCommented Oct 15, 2018 at 17:04
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Yes, this is known. For $d = \Omega(n^{1/2})$ with a sufficiently large implicit constant, any $n$-node graph of average degree $d$ has $\Omega(d^4)$ total $C_4$s. This is best possible because it's realized by a random graph.
The earliest reference I'm aware of for this is "Cube-Supersaturated Graphs and Related Problems" by Erdos and Simonovits, where it's claimed without proof. There are many proofs out there, off the top of my head see Lemma 3 here.
