Demuestre que la suma de los números de ordenadas $3$ -cliques y $3$ -anticliques no es inferior a $\binom{V}{3}+\frac{2E^2}{V}-E(V-1)$ .

Question

Demuestre que la suma del número de ordenadas $3$ -cliques y el número $3$ -anticliques en un gráfico no es inferior a $$\binom{V}{3}+\frac{2E^2}{V}-E(V-1)\,.$$

Tengo un problema con esta tarea, porque no sé por dónde empezar. ¿Puedes darme una pista (qué teorema me ayudará o qué debo contar (camarillas o anticlillas) al principio) ¡Muchas gracias por la ayuda!

Answer 1

Sea $G(V,E)$ sea un grafo (simple) sobre el conjunto $V$ de $n$ vértices con el conjunto de aristas $E$ compuesto por $m$ bordes. Sea $s$ y $t$ denotan, respectivamente, el número de $3$ -cliques y el número de $3$ -anticliques de $G$ .

A pierna es un vértice junto con dos vértices vecinos (distintos), a saber, un par $\big(u,\{v,w\}\big)$ con $u,v,w\in V$ y $v\neq w$ tal que $\{u,v\}$ y $\{u,w\}$ son aristas de $G$ . Un antipiernas es un vértice junto con dos vértices (distintos) no vecinos, a saber, un par $\big(u,\{v,w\}\big)$ con $u,v,w\in V$ y $v\neq w$ de forma que ni $\{u,v\}$ ni $\{u,w\}$ es una arista de $G$ . Escriba a $L$ y $A$ para el conjunto de patas y el conjunto de antipatas en $G$ respectivamente.

Si $d_v$ denotan el grado de $v\in V$ demuestre que $$|L|=\sum_{v\in V}\,\binom{d_v}{2}\geq n\,\binom{\frac{1}{n}\,\sum_{v\in V}\,d_v}{2}=n\,\binom{\frac{2m}{n}}{2}=m\left(\frac{2m-n}{n}\right)\,.$$ Existen $\displaystyle \binom{n}{3}-s$ triples de vértices en $G$ que no forman $3$ -cliques. Cada uno de estos triples es responsable de un tramo como máximo, mientras que un $3$ -clique crea tres piernas. Eso es, $$|L|\leq 1\cdot\Biggl(\binom{n}{3}-s\Biggr)+3\cdot s=\binom{n}{3}+2s\,.$$ En consecuencia, $$s\geq \frac{m}{2}\,\left(\frac{2m-n}{n}\right)-\frac{1}{2}\,\binom{n}{3}=\frac{m^2}{n}-\frac{m}{2}-\frac{1}{2}\,\binom{n}{3}\,.\tag{*}$$

Del mismo modo, tenemos $$|A|=\sum_{v\in V}\,\binom{(n-1)-d_v}{2}\geq n\,\binom{(n-1)-\frac{1}{n}\,\sum_{v\in V}\,d_v}{2}\,,$$ o $$|A|\geq n\,\binom{n-1-\frac{2m}{n}}{2}=3\,\binom{n}{3}+\frac{2m^2}{n}-2mn+3m\,.$$ También tenemos $$|A|\leq 1\cdot\Biggl(\binom{n}{3}-t\Biggr)+3\cdot t=\binom{n}{3}+2t\,.$$ Por lo tanto, $$t\geq \frac{3}{2}\,\binom{n}{3}+\frac{m^2}{n}-mn+\frac{3}{2}m\,.\tag{#}$$ Combinando (*) y (#), obtenemos $$s+t\geq \binom{n}{3}+\frac{2m^2}{n}-mn+m=\binom{n}{3}+\frac{2m^2}{n}-m(n-1)\,.$$

En particular, para $n=6$ tenemos $$s+t\geq 20+\frac{m^2}{3}-5m=\frac{1}{3}\,\left(m-\frac{15}{2}\right)^2+\frac{5}{4}\geq \frac{5}{4}\,.$$ Por lo tanto, en cualquier grafo simple sobre $6$ vértices, hay dos $3$ -cliques, o dos $3$ -anticliques, o una $3$ -clique y uno $3$ -anticlique. Este resultado implica un caso especial de Teorema de Ramsey .