Límite inferior

Question

Deje $G=(V,E)$ ser $n$-vértice de la gráfica con $e$ bordes.

Para todos los $v\in V$, $d(v)$ es el grado de $v$, e $\bar{d}(v)$ es el `sin título" de $v$, es decir, $\bar{d}(v)=(n-1)-d(v)$ (el grado de $v$ en el complemento de $G$).

Definir $k:=\left\lceil\sqrt{2e+1/4}+1/2\right\rceil$.

Quiero mostrar que \begin{align*} \sum_{v\in V}d(v)\bar{d}(v) & \geq 2(n-2)e - \frac{1}{4}\left(k^4-6k^3-(4e-11)k^2+(20e-6)k+4e(e-7)\right) \\ & = 2(n-2)e - \left(\binom{k}{2}-e\right)^2 + (4k-7)\left(\binom{k}{2}-e\right) - 6\binom{k}{3} \end{align*}

Voy a explicar donde esta el límite inferior viene. Creo que el gráfico, se $G^*$, que alcanza este límite inferior es la siguiente construcción:

Tomar un solo vértice de un $k$-camarilla (un grafo completo con $k$ vértices) y quitar exactamente $r=\binom{k}{2}-e$ aristas incidentes a ella. Ahora agregue $n-k$ aislado de los vértices. En ese caso, hay un vértice de grado $k-r-1$hay $r$ vértices de grado $k-2$hay $k-r-1$ vértices de grado $k-1$, e $n-k$ vértices de grado $0$. Por lo tanto, para esta construcción, \begin{align*} \sum_{v\in V}d(v)\bar{d}(v) & = (k-r-1)\left(n-1-(k-r-1)\right) + r(k-2)\left(n-1-(k-2)\right) + (k-r-1)(k-1)\left(n-1-(k-1)\right) \\ & = (k-r-1)(n-k+r) + r(k-2)(n-k+1) + (k-r-1)(k-1)(n-k) \\ & = n(k^2-k-2r) - (k-r)(k-r-1) - r(k-1)(k-2) - k(k-1)(k-r-1) \\ & = 2en - 4e + 4e - r^2 +r(4k-3) - k^3 + k^2 \\ & = 2(n-2)e - \left(\binom{k}{2}-e\right)^2 + (4k-7)\left(\binom{k}{2}-e\right) + 4\binom{k}{2} - k^3 + k^2 \\ & = 2(n-2)e - \left(\binom{k}{2}-e\right)^2 + (4k-7)\left(\binom{k}{2}-e\right) - 6\binom{k}{3} \end{align*}

Podría alguien ayudarme a demostrar que $G^*$ es de hecho el "mejor" de la construcción, con "el mejor", es decir, $G^*$ es el único gráfico que minimiza $\sum_{v \in V} d(v) \bar{d}(v)$ entre todos los $n$-vértice gráficos con $e$ bordes. Gracias por tu ayuda!!

Answer 1

Yo no verificación de las ecuaciones en detalle, pero la construcción que se describe no minimizar $\sum_v d(v) \bar{d}(v)$ para el caso de $n=5, e=4$. Para este caso:

• $k:=\left\lceil\sqrt{2e+1/4}+1/2\right\rceil = \left\lceil\sqrt{8.25}+1/2\right\rceil = 4$

• $r = {k \choose 2} - e = {4 \choose 2} - 4 = 6 - 4 = 2$

Por su construcción, se empieza con la $4$-camarilla (más comúnmente denotado $K_4 =$ gráfico completo de $4$ nodos), elija uno de los nodos $w$ (grado $3$) y retire $2$ de sus bordes. Puedes terminar con un $3$-ciclo (el otro $3$ recogidos nodos) y de un solo filo conectar $w$ a uno de los nodos en el ciclo. Entonces a partir de la $n=5$ agregar $1$ aislado de nodo. Llamamos a esta resultando $n=5, e=4$ gráfico $A$. Los cinco nodo grados de $A$ son: $0, 1, 2, 2, 3$ y la suma es $sum(A) = 0+3+4+4+3 = 14$.

Sin embargo, la estrella de la gráfica de $B$ (donde un centro de nodo se conecta a todos los demás y esas son todas las conexiones) de $n=5, e=4$ ha nodo grados $1,1,1,1,4$ y la suma es $sum(B) =3+3+3+3+0 = 12 < sum(A)$.

---

Creo que su construcción tiene mucho mérito, en realidad, pero se ha perdido un hecho clave:

Como usted señaló, $\bar{d}(v)$ es el grado de $v$ en el complemento gráfico de $G' = (V, E')$ (es decir, donde $e \in E'$ fib $e \notin E$). Por lo tanto, la suma de $\sum_v d(v) \bar{d}(v)$ realmente es el mismo si usted se considera a $G$ o $G'$, ya que el complemento de $G'$ es $G$ nuevo. I. e. $\forall G: sum(G) = sum(G')$.

Sin embargo, $e' = |E'| = {n \choose 2} - e$, y así que si usted comienza su procedimiento de construcción con $e$ o $e'$ se obtendrá de dos diferentes gráficos (obviamente). Resulta que son no se complementa el uno del otro, y puede tener distintos valores para la suma.

Mi ejemplo es exactamente eso. Si hacemos uso de su construcción, pero empezar con $n=5, e'=6$, tendríamos:

• $k':=\left\lceil\sqrt{2e'+1/4}+1/2\right\rceil = \left\lceil\sqrt{12.25}+1/2\right\rceil = \lceil 3.5 + 0.5 \rceil = 4$

• $r' = {k' \choose 2} - e' = {4 \choose 2} - 6 = 6 - 6 = 0$

Así empezamos con $K_4$, quitar ninguno de sus bordes, y simplemente añadir un $5$th aislado nodo. Este gráfico, $C$, ha nodo grados se $3,3,3,3,0$ e $sum(C) = 3 + 3+ 3+ 3+ 0 = 12$. Desde $C$ ha $6$ bordes, no califica, pero su complementar $C'$ ha $4$ bordes y no calificar, y ya sabemos $sum(C') = sum(C) = 12$. Ahora, ¿cuál es $C'$? Es exactamente mi estrella gráfico de $B$.

Para concluir: incluso si usted piensa que su procedimiento es grande, después de que la utilice en la $(n, e)$ para obtener un gráfico de $A$, usted debe también repetir el procedimiento a partir del con $(n, e' = {n \choose 2} - e)$ y obtener un gráfico diferente $C$. Se garantiza que las $C'$ ha $e$ bordes. Así que debes elegir la $\min( sum(A), sum(C') )$.

Creo que es una interesante pregunta de si esta doble estrategia será siempre de minimizar la suma de un determinado $(n,e)$.

Answer 2

Aquí hay una rápida prueba de que $G^*$ es óptimo. Estamos tratando de maximizar $\sum \limits_{v \in V} (n-1)d(v) - d(v)^2$, señalando que $\sum \limits_{v \in V} d(v) = 2e$. Ya que la función $(n-1)x-x^2$ es cóncava, si cualquiera de los dos valores de $d(v)$ difieren por lo menos dos, acercándolas por $1$ mejoraría nuestra suma. Así que la máxima suma posible ocurriría cuando todos los $d(v)$ estaban dentro de $1$ de cada uno de los otros y, por tanto, tomar uno de dos valores posibles, que es exactamente el importe obtenido por $G^*$.