Количество 4 циклов

Пусть $C_4$ - цикл с четырьмя вершинами. Для произвольного графа $G$ с $n$ вершинами и m ребрами скажем $m>n\sqrt n$ , сколько существует$C_4$? Есть ли нижняя граница для этого?

Да, это известно. Для $d = \Omega(n^{1/2})$ с достаточно большой неявной константой, любой $n$ -node графики средней степени $d$ имеют $\Omega(d^4)$ общие $C_4$ с. Это лучше всего возможно, потому что это реализуется случайным графом.

Самое раннее упоминание, о котором мне известно, это «Пересыщенные кубом графы и связанные с ними проблемы» Эрдоса и Симоновича, где они заявлены без доказательств. Есть много доказательств, с верху моей головы, см. Лемму 3 здесь .