Contando triángulos en una gráfica o su complemento.

Question

Dado un simple gráfico de $G$ [sin lazos ni aristas paralelas] en los seis vértices, deje $G^c$ el valor de su complemento. Es conocido que cualquiera de las $G$ o $G^c$ debe contener un triángulo $T$ . [Un ejemplo de un número de Ramsey creo.]

Mi pregunta surgió cuando traté de encontrar una gráfica de seis vértices que sólo tenía una $T$ o su complemento. Creo que si hice las cosas bien no hay ninguno de estos. Este traté de comprobar mediante el dibujo de una copia de cada gráfico de $G$ en los seis vértices que tiene un $T$ en ella, y luego busca en la complementa para ver si había no $T$'s en ellos. Yo no he encontrado ninguna.

Una manera de plantear mi pregunta para un número general $n$ de vértices es entonces de la siguiente manera: Consideremos el conjunto de todos los gráficos $G$ $n$ vértices, y para cada uno de constructo $G^c.$ Contar el número de $T$ $G$ y añadir que el número de $T$ $G^c.$ Finalmente, encontrar el mínimo de dicha suma para el $n$ y la llamada que decir $M(n).$ Para mi por encima de los seis vértices conjetura es que $M(6)=2.$

Considerando un ciclo de la gráfica de cinco vértices nos encontramos con $M(5)=0.$

Así que más de uno podría preguntar si nada se sabe acerca de este mínimo de la función $M(n)$ grandes $n$ [tales como límites, etc.] Y ¿tiene un nombre?

También me gustaría ver una manera más simple de manejar los seis vértices caso, uno que no impliquen el dibujo de todas las gráficas.

Answer 1

Supongamos que cada borde de $K_n$ es de color rojo o azul. Deje $r_i$ $b_i$ denotar el rojo de grado y el azul del grado del vértice $v_i.$ Deje $t$ denotar el número de no-monocromática triángulos, es decir, triángulos tener al menos uno de los bordes de cada color. Deje $a$ denotar el número de $2$-color-de-los ángulos, es decir, pares de $\{e,f\}$ donde $e$ $f$ son bordes adyacentes de diferentes colores. Observar que $$2t=a=\sum_{i=1}^nr_ib_i.\tag1$$ Caso I. $n$ es incluso, decir $n=2k.$

Entonces la suma (1) se maximiza cuando se $\{r_i,b_i\}=\{k,k-1\}$ por cada $i,$ y que en caso de $$t=\frac12\sum_{i=1}^{2k}k(k-1)=k^2(k-1),$$ y por lo que el número de monocromático triángulos es $$M(2k)=\binom{2k}3-k^2(k-1)=\frac{k(k-1)(k-2)}3.$$ Ejemplo. Para $n=6$ el número mínimo de monocromático triángulos es $2.$

Caso II. $n=4k+1.$

La suma (1) se maximiza cuando se $r_i=b_i=2k$ por cada $i,$ y que en caso de $$t=\frac12\sum_{i=1}^{4k+1}(2k)^2=2k^2(4k+1),$$ y por lo que el número de triángulos es monocromática $$M(4k+1)=\binom{4k+1}3-2k^2(4k+1)=\frac{2k(k-1)(4k+1)}3.$$ Caso III. $n=4k+3.$

No es posible tener $r_i=b_i=2k+1$ todos los $i,$ desde $2k+1$ $n=4k+3$ son ambos impares. La suma (1) se maximiza cuando se $r_i$ $b_i$ son casi iguales como sea posible, por ejemplo, cuando se $\{r_1,b_1\}=\{2k,2k+2\}$ $r_i=b_i=2k+1$ todos los $i\ne1.$ En el caso $$t=\frac12\left[(2k)(2k+2)+\sum_{k=2}^{4k+3}(2k+1)^2\right]=2k(k+1)+(2k+1)^3=8k^3+14k^2+8k+1,$$ y por lo que el número de triángulos es monocromática $$M(4k+3)=\binom{4k+3}3-(8k^3+14k^2+8k+1)=\frac{8k^3+6k^2-2k}3.$$

La construcción de extremal gráficos. En los casos I y II podemos tomar $G=C_n^{\lfloor n/4\rfloor}$ para la gráfica roja. En caso III empezamos con $C_{4k+3}^k$ e (con vértices numerados de forma cíclica) añadir el $2k+1$ bordes $v_2v_{2k+3},\ v_3v_{2k+4},\dots,\ v_{2k+2}v_{4k+3}.$

Las referencias. La función de $M(n)$ es OEIS secuencia A014557; la fórmula general es $$M(n)=\binom n3-\left\lfloor\frac n2\left\lfloor\left(\frac{n-1}2\right)^2\right\rfloor\right\rfloor;$$ la referencia original es:

A. W. Goodman, En conjuntos de conocidos y extraños, en cualquier parte, Amer. De matemáticas. Mensual 66 (1959), 778-783.