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.


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.