Return to Answer

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 an acyclic graph 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 make them closer with sum being fixed'. Each such move corresponds to similar changes of the multiset of $k$-wise sums.

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.

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 an acyclic graph for any convex function $f$. In other words, if we associate with our tournament $T_n$ the multiset $M_k(T)$ of $\binom{n}k$ numbers $ \sum_{i\in X}\deg(i)$, where $X$ runs over $k$-subsets of $X$, 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\}$ of 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 make them closer with sum being fixed'. Each such move corresponds to similar changes of the multiset of $k$-wise sums.

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 an acyclic graph 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 make them closer with sum being fixed'. Each such move corresponds to similar changes of the multiset of $k$-wise sums.

Note that $\prod_{i\in X,j\notin X}a_{ij}=r^{-\binom{k}2}\prod_{i\in X} r^{\deg(i)}$, where $\deg$ is out-degree of $i$ in the tournament defined by ``draw an arrow from $i$ to $j$ whenever $a_{ij}=r$''. Clearly the multiset of degrees is majorized by the multiset $\{0,1,\dots,n-1\}$ of degrees in an acyclic tournament. I claim 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 implies your claim by Karamata's inequality (for the function $e^x$). The claim follows from the following observation: $B$ is obtained from $A$ by a sequence of moves 'take two elements and make them closer with fixed sum'. Each move corresponds to similar changes of $k$-wise sums.

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 an acyclic graph for any convex function $f$. In other words, if we associate with our tournament $T_n$ the multiset $M_k(T)$ of $\binom{n}k$ numbers $ \sum_{i\in X}\deg(i)$, where $X$ runs over $k$-subsets of $X$, 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\}$ of 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 make them closer with sum being fixed'. Each such move corresponds to similar changes of the multiset of $k$-wise sums.