number of 4 cycles

2018-10-15 15:14:47

Let $C_4$ be a cycle with $4$ 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?

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.

  • 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.

    2018-10-15 15:34:34