Maximizar la suma de productos de la variable binaria

Question

Dejemos que $n>k$ sean enteros positivos, $r>1$ un número real positivo, y $A=\{1,2,\dots,n\}$ . Para $1\leq i\neq j\leq n$ , dejemos que $a_{i,j}\in\{r,1\}$ sea tal que $a_{i,j}=r\Leftrightarrow a_{j,i}=1$ . Considere la suma $$S=\sum_{X\subseteq A, |X|=k}\prod_{i\in X, j\in A\backslash X}a_{i,j}.$$

¿Es cierto que $S$ se maximiza cuando $a_{i,j}=r$ para todos $i<j$ ?

Obsérvese que el número de pares ordenados $(i,j)$ tal que $a_{i,j}=r$ es fijo (es decir, la mitad de todos los pares); lo mismo ocurre con $a_{i,j}=1$ . Por lo tanto, debería ser óptimo agrupar el mayor número de términos iguales a $r$ como sea posible en el mismo producto.

Answer 1

Se trata de un torneo (dibujar una flecha desde $i$ a $j$ siempre que $a_{ij}=r$ ) y quiere demostrar que su suma es maximizada para un torneo acíclico $AC_n$ .

Denota por $\deg(i)$ el grado de salida de $i$ . Entonces $$\prod_{i\in X,j\notin X}a_{ij}=r^{-\binom{k}2}\prod_{i\in X} r^{\deg(i)}=f\left(\sum_{i\in X}\deg(i)\right)$$ para una función convexa $$f(t)=r^{-\binom{k}2+t}.$$

Afirmo que dicha suma se maximiza en $AC_n$ para cualquier función convexa $f$ . En otras palabras, si asociamos a nuestro torneo $T_n$ el multiconjunto $M_k(T_n)$ de $\binom{n}k$ números $\sum_{i\in X}\deg(i)$ , donde $X$ se pasa por encima $k$ -subconjuntos de $\{1,\dots,n\}$ entonces $M_k(AC_n)$ se especializa $M_k(T_n)$ .

Al principio, lo establecemos para $k=1$ . Este caso significa que el conjunto de grados de $T_n$ es mayoritaria por el conjunto múltiple $\{0,1,\dots,n-1\}$ (grados de $AC_n$ ). De hecho, para cualquier $m=1,\dots,n$ la suma de grados de cualquier $m$ vértices de $T_n$ es al menos $\binom{m}2=0+1+\dots+(m-1)$ (ya que la suma de grados es al menos el número de aristas entre estos $m$ vértices). Esto significa (por la propia definición), que el conjunto de grados de $T_n$ es mayoritaria en $0,1,\dots,n-1$ .

Ahora basta con demostrar que si un conjunto múltiple $A=\{a_1,\dots,a_N\}$ mayoriza otro multiconjunto $B=\{b_1,\dots,b_N\}$ entonces lo mismo ocurre con su $k$ -suma en sentido estricto (sin repeticiones): $a_{i_1}+\dots+a_{i_k}$ , $i_1<\dots<i_k$ ). Se deduce de la siguiente observación: $B$ se obtiene de $A$ mediante una secuencia de movimientos "toma dos elementos desiguales y los une con la suma que se fija". Cada uno de estos movimientos corresponde a cambios similares del conjunto múltiple de $k$ -sumas.