Maximize sum of products of binary variable

Question

Let $n>k$ be positive integers, $r>1$ a positive real number, and $A=\{1,2,\dots,n\}$. For $1\leq i\neq j\leq n$, let $a_{i,j}\in\{r,1\}$ be such that $a_{i,j}=r\Leftrightarrow a_{j,i}=1$. Consider the sum $$S=\sum_{X\subseteq A, |X|=k}\prod_{i\in X, j\in A\backslash X}a_{i,j}.$$

Is it true that $S$ is maximized when $a_{i,j}=r$ for all $i<j$?

Observe that the number of ordered pairs $(i,j)$ such that $a_{i,j}=r$ is fixed (i.e. half of all the pairs); the same holds for $a_{i,j}=1$. Therefore it should be optimal to group as many terms equal to $r$ as possible in the same product.

Answer 1

We deal with a tournament (draw an arrow from $i$ to $j$ whenever $a_{ij}=r$) and want to prove that your sum is maximized for an acyclic tournament $AC_n$.

Denote by $\deg(i)$ the out-degree of $i$. Then $$\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)$$ for a convex function $$f(t)=r^{-\binom{k}2+t}.$$

I claim that such a sum is maximized on $AC_n$ for any convex function $f$. In other words, if we associate with our tournament $T_n$ the multiset $M_k(T_n)$ of $\binom{n}k$ numbers $\sum_{i\in X}\deg(i)$, where $X$ runs over $k$-subsets of $\{1,\dots,n\}$, then $M_k(AC_n)$ majorizes $M_k(T_n)$.

At first, we establish this for $k=1$. This case means that the multiset of degrees of $T_n$ is majorized by the multiset $\{0,1,\dots,n-1\}$ (degrees of $AC_n$). Indeed, for any $m=1,\dots,n$, the sum of degrees of any $m$ vertices of $T_n$ is at least $\binom{m}2=0+1+\dots+(m-1)$ (since the sum of degrees is at least the number of edges between these $m$ vertices). This means (by the very definition), that the multiset of degrees of $T_n$ is majorized by $0,1,\dots,n-1$.

Now it suffices to prove that if one multiset $A=\{a_1,\dots,a_N\} $ majorizes another multiset $B=\{b_1,\dots,b_N\}$, then the same holds for their $k$-wise sums (without repetitions: $a_{i_1}+\dots+a_{i_k}$, $i_1<\dots<i_k$). It follows from the following observation: $B$ is obtained from $A$ by a sequence of moves 'take two unequal elements and bring them together with the sum being fixed'. Each such move corresponds to similar changes of the multiset of $k$-wise sums.