Demostrar que $x\ge n(n-1)(n-3)/8$, donde $x$ es el número de ciclos de $C_4$ en un gráfico.

Question

Si hay que no ciclos $C_4$ en un gráfico de los bordes en $G$, es decir, $e(G)\le\frac n4(\sqrt{4n-3}+1)$, pero si $e(G)\ge\frac12 {n \choose 2}$, tenemos que demostrar $x$(número de ciclos de $c_4$) $\ge n(n-1)(n-3)/8$. Sé que tenemos que encontrar la diferencia de los bordes también números de ciclos de longitud 4 ${n \choose 4}\cdot \frac{3!}2$ (donde $n \choose 4$ es para tener en cuenta para la selección de $4$ y $3!$ modos de selección y división de $2$ para eliminar ciclos de reversos). Pero soy incapaz de incorporar la condición de los bordes y encontrar mi resultado.

Answer 1

Solución incompleta: Esta solución sólo funciona para $n\geq 15$.

Escribir $V$ $E$ para el conjunto de vértices y el conjunto de aristas de $G$, respectivamente. Vamos $n:=|V|$, $m:=|E|$, y $x$ el número de $4$-ciclos en $G$. Para $v\in V$, escribir $d_v$ para el grado de $v$. Deje $S$ ser el conjunto de todos los pares de $\big(u,\{v,w\}\big)$ donde $u,v,w \in V$ son tales que $v\neq w$$\{u,v\}$$\{u,w\}$$E$.

Para una fija $u\in V$, $\binom{d_u}{2}$ conjuntos de la forma $\{v,w\}\in\binom{V}{2}$ tal que $\{u,v\},\{u,w\}\in E$. Por lo tanto, $|S|=\sum_{u\in V}\,\binom{d_u}{2}$. Ahora, para $\{v,w\}\in\binom{V}{2}$, vamos a $t_{\{v,w\}}$ el número de $4$-ciclos que $v$ $w$ son vértices opuestos. Tenga en cuenta que $\sum_{\{v,w\}\in\binom{V}{2}}\,t_{\{v,w\}}=2x$. Además, para$\{v,w\}\in\binom{V}{2}$, $t_{\{v,w\}}=\binom{r_{\{v,w\}}}{2}$ donde $r_{\{v,w\}}$ es el número de la común de los vértices vecinos de $v$$u$. Claramente, $|S|=\sum_{\{v,w\}\in \binom{V}{2}}\,r_{\{v,w\}}$.

Observar que $\left|r_{\{v,w\}}-\frac{1}{2}\right|=\sqrt{2\,t_{\{v,w\}}+\frac{1}{4}}$, lo $r_{\{v,w\}}\leq \frac{1}{2}+ \sqrt{2\,t_{\{v,w\}}+\frac{1}{4}}$. Por lo tanto, $$|S| \leq \sum_{\{v,w\}\in\binom{V}{2}}\left(\frac{1}{2}+ \sqrt{2\,t_{\{v,w\}}+\frac{1}{4}}\right)=\frac{1}{2}\binom{n}{2}+\sum_{\{v,w\}\in\binom{V}{2}}\sqrt{2\,t_{\{v,w\}}+\frac{1}{4}}\,.$$ Debido a la concavidad de la función de $t\mapsto\sqrt{t}$$t\in[0,\infty)$, por la Desigualdad de Jensen que $$|S| \leq \frac{1}{2}\binom{n}{2}+\binom{n}{2}\sqrt{\frac{1}{\binom{n}{2}}\sum_{\{v,w\}\in\binom{V}{2}}\left(2\,t_{\{v,w\}}+\frac{1}{4}\right)}=\frac{1}{2}\binom{n}{2}+\binom{n}{2}\sqrt{\frac{4x}{\binom{n}{2}}+\frac{1}{4}}\,.$$

Por el Cauchy-Schwarz Desigualdad, $|S|=\sum_{u\in V}\,\binom{d_u}{2} \geq n\,\binom{\frac{1}{n}\sum_{u\in V}\,d_u}{2}=n\,\binom{2m/n}{2}=m\left(\frac{2m}{n}-1\right)$. Es decir, $\frac{1}{2}\binom{n}{2}+\binom{n}{2}\sqrt{\frac{4x}{\binom{n}{2}}+\frac{1}{4}}\geq |S| \geq m\left(\frac{2m}{n}-1\right)$. Ergo, si $m$ es lo suficientemente grande (es decir, $m \geq \frac{n}{4}\left(1+\sqrt{4n-3}\right)$), luego $$x \geq \frac{m}{4}\left(\frac{2m}{n}-1\right)\left(\frac{m}{\binom{n}{2}}\left(\frac{2m}{n}-1\right)-1\right)\,.$$ En particular, si $m\geq\frac{1}{2}\binom{n}{2}$$n\geq 7$, luego tenemos $$x \geq \frac{1}{8}n(n-1)\left(\frac{n-1}{2}-1\right)\left(\frac{1}{2}\left(\frac{n-1}{2}-1\right)-1\right)=\frac{n(n-1)(n-3)(n-7)}{64}\,.$$ Si $n\geq 15$,$\frac{n-7}{8}\geq 1$, lo $x\geq\frac{n(n-1)(n-3)}{8}$.

P. S. Para $n \leq 3$, la desigualdad de $x\geq\frac{n(n-1)(n-3)}{8}$ es vacuously verdadero. Para $4\leq n\leq 10$, la desigualdad de $x\geq\frac{n(n-1)(n-3)}{8}$ es falso (no son fáciles de contraejemplos). Yo estoy cansado de buscar por otros contraejemplos, pero creo que la desigualdad es falsa por $n=11,12,13$ (pero no seguro para $n=14$).

Answer 2

Lema. Si $a_i\in\mathbb N_0$ $1\le i\le N$ $\sum a_i\ge M>0$ $$\sum_{i=1}^N{a_i \choose 2}\ge \frac{(M-N)M}{2N}$$

Prueba. El uso de la QM-SOY la desigualdad $$ \frac{\sum_i a_i^2}N\ge \left(\frac{\sum_i a_i}{N}\right)^2$$ nos encontramos $$\begin{align}2 \sum_{i=1}^N{a_i \choose 2} &=\sum a_i^2-\sum a_i\\ &\ge\frac1N\left(\sum a_i\right)^2-\sum a_i\\ &=\left(\frac 1N\sum a_i-1\right)\sum a_i\\ &\ge \frac{(M-N)M}{N}\end{align}$$ donde la última desigualdad se justifica incluso cuando el expressin en paréntesis es negativo debido a que el lado izquierdo es, ciertamente, no negativo. $_\square$

Cada vértice de grado $d$ da lugar a ${d\choose 2}$ caminos de longitud $2$. Así que usando el lema con $\sum_v d(v)=2e(G)\ge\frac{n(n-1)}2$, el número de caminos de longitud 2 es $$ n_2\ge\frac{(\frac{n(n-1)}2-n)\frac{n(n-1)}2}{2n}=\frac{n(n-1)(n-3)}{8}$$

Para dos vértices $a,b$ deje $f(a,b)$ el número de $2$-caminos de $a$ $b$(es decir, el número de la común de vecinos). Entonces $$\sum_{\{a,b\}}f(a,b)=n_2\ge \frac{n(n-1)(n-3)}8$$ y $$2x = \sum_{\{a,b\}}{f(a,b)\choose 2}$$ así que por el lema $$x \ge \frac{(\frac{n(n-1)(n-3)}8-{n\choose 2})\frac{n(n-1)(n-3)}8}{2{n\choose 2}} =\frac{n(n-1)(n-3)(n-7)}{64}.$$ Para $n\ge 15$, esto implica que el resultado deseado.

Después de deshacerse de los errores Batominovski amablemente me di cuenta, el resultado es el mismo que el de él. :(