Maximización de la suma de los productos de los extremos de las aristas de un grafo

Question

Dejemos que $G$ sea un gráfico con un conjunto de vértices $V=\{v_1,v_2\dots v_n\}$ y conjunto de bordes $E$ . Sea $f:V\rightarrow \mathbb [0,\infty)$ sea una función de valor real tal que $\sum\limits_{i=1}^n f(v_i)=A$ .

¿Cuál es el valor máximo posible para $\sum\limits_{uv\in E}f(u)f(v)$ ?

Recuerdo haber visto una prueba chapucera hace un par de años que era $\frac{A^2(k-1)}{2k}$ donde $k$ es el número de camarilla de $G$ .

Es evidente que se trata de un límite inferior para el máximo, pero tengo problemas para demostrar que es el máximo real. Podemos ver que es un límite inferior tomando una camarilla máxima y dejando que $f(v)=\frac{1}{k}$ si el vértice está en la camarilla y $0$ en otro lugar.

Answer 1

Esta es esencialmente la misma prueba que la del sueño, pero formulada de una manera geométrica genial.

Dejemos que $A=1$ para simplificar. Rotulemos los vértices de $V$ como $1, 2, \ldots, n$ y notemos el valor de $f(v)$ por $x_v$ . El problema se convierte entonces en el problema de optimización $\mathrm{OPT}(E)$ dado por

$$\max_{x\in \triangle^n} P_E(x)$$

donde $P_E(x)$ es el polinomio homogéneo de grado 2 $P_E(x) = \sum_{uv\in E} x_ux_v$ y donde $\triangle^n$ es el estándar $n$ -simplemente . Para $x \in \triangle^n$ que el soporte de $x$ sea el subconjunto $S(x)\subseteq V$ definido por $u\in S(x)$ si $x_u>0$ . Sea $M$ sea el subconjunto (no vacío) de $\triangle^n$ donde $P_E(x)$ se maximiza, y dejemos que $M^*$ sea el subconjunto de $M$ que contiene puntos de apoyo mínimo. Sea $\ell_{uv}(x)$ denotan la línea que pasa por $x$ en paralelo a $\boldsymbol{e}_u - \boldsymbol{e}_v$ .

Afirmamos que $S(x^*)$ es una camarilla para todo $x^*\in M^*$ . Para ver esto, observe que el gradiente direccional de $P_E(x)$ evaluado en algún momento $x$ en la cuerda floja $\ell_{uv}(x^*)$ en la dirección de $\ell_{uv}(x^*)$ viene dada por

$$\nabla P_E(x)\cdot(\boldsymbol{e}_u - \boldsymbol{e}_v) = \sum_{w\in N(u)} x_w - \sum_{w\in N(v)} x_w$$

para todos $u,v\in S(x^*)$ . Si $(u,v) \notin E$ entonces esta expresión se evalúa como una constante, ya que $x_w$ para $w\notin \{u,v\}$ se fija para todos los $x\in \ell_{uv}$ . Pero si es una constante, entonces $\ell_{uv}\cap \partial \triangle^n$ contendría un punto en $M$ de menor apoyo, contradiciendo la minimización de $M^*$ . Así, $(u,v) \in E$ para todos $u, v \in S(x^*)$ como se ha reclamado.

De hecho, si $x\in M^*$ exigimos que el gradiente direccional de $P_E(x)$ en la dirección $\ell_{uv}(x)$ es $0$ para todos $u,v\in S(x)$ ya que $x \notin \ell_{uv}\cap \partial \triangle^n$ . Así,

$$ 0 = \nabla P_E(x^*)\cdot(\boldsymbol{e}_u - \boldsymbol{e}_v) = \sum_{w\in N(u)} x_w - \sum_{w\in N(v)} x_w = x_v - x_u $$ con la última igualdad derivada de la condición de camarilla. Esto demuestra que el $x_u$ es una constante $\forall u \in S(x)$ y, por tanto, que $\mathrm{OPT}(E) = \frac{k'-1}{k'}$ , donde $k' = \lvert S(X) \rvert$ . Esta cantidad se maximiza tomando $S(x)$ para ser un máximo $k$ -clique.

Answer 2

He conseguido resolverlo con la ayuda de fractal en AOPS.

Para cada función $f:V\rightarrow [0,\infty)$ con las propiedades deseadas deje $pos(f)$ sea $\{v\in V|f(v)>0\}$ .

Ahora, consideremos el conjunto de todas esas funciones en $f$ tal que $\sum\limits_{uv\in E}f(u)f(v)$ alcanza el máximo-

Toma $f$ sea una de las funciones de este conjunto, de modo que $|pos(f)|$ es mínima.

Supongamos que $pos(f)$ no induce una camarilla, entonces hay vértices $a,b\in pos(f)$ que no están conectados por una arista.

Ahora podemos escribir $\sum\limits_{uv\in E}f(u)f(v)=c_1+c_2f(a)+c_3f(b)$ . En el sitio web $c_1$ es la suma de los productos de los puntos finales de todas las aristas que no incluyen $a$ o $b$ , $c_2$ es la suma de $f(x)$ sobre todos los vecinos $x$ de $a$ y $c_3$ es la suma de $f(x)$ sobre todos los vecinos $x$ de $b$ .

Así que, básicamente, los bordes que no contienen $a$ o $b$ más las aristas que contienen $a$ más las aristas que contienen $b$ . Así que si suponemos $c_2\geq c_3$ entonces la función $f'$ definido como $f'(x)=f(x)$ si $x\neq a,b$ y $f'(a)=f(a)+f(b)$ y $f'(b)=0$ cumple las tres condiciones siguientes:

$\sum\limits(u\in V)f(u) =A $ .

$\sum\limits_{uv\in E}f(u)f(v)\leq \sum\limits_{uv\in E}f'(u)f'(v)$ .

$pos(f')<pos(f)$ .

Contradiciendo la minimización de $|pos(f)|$ .

Así que podemos encontrar una función que alcance el máximo y satisfaga que $pos(f)$ induce una camarilla.

Así que ahora dejemos $f$ sea una función tal que $pos(f)$ es una camarilla con un conjunto de vértices $\{w_1,w_2\dots w_k\}$ . Entonces queremos maximizar:

$\sum\limits_{1\leq i<j\leq k}f(w_i)f(w_j)=\frac{(w_1+w_2+\dots w_k)^2-(w_1^2+w_2^2 + \dots + w_k^2)}{2}=\frac{A^2-(w_1^2+w_2^2 + \dots + w_k^2)}{2}$ .

Así que queremos minimizar la suma de cuadrados, por la desigualdad de Jensen o alternativamente por AM-QM esto ocurre cuando $w_i=\frac{A}{k}$ para $1\leq i\leq k$ . Y en este caso la suma deseada se convierte en $\frac{A^2-k(A/k)^2}{2}=\frac{A^2(k-1)}{2k}$ . Evidentemente, esto se hace más grande a medida que $k$ se hace más grande, por lo que el máximo se alcanza cuando $k$ es el número de camarilla, como se desea.