Expectation inequality for sampling without replacement

Question

Is the following proposition correct?

$X_1, X_2, X_3$ are uniformly at random sampled from a finite set $\mathcal X$ without replacement. $f : \mathcal X^2 \rightarrow \mathbb R_{\ge0}$ is symmetric: $ f(x, y) = f(y, x) $, then:

$$ \mathbb E_{X_1, X_2, X_3} f(X_1, X_2) f(X_1, X_3) f(X_2, X_3) \le ( \mathbb E_{X_1, X_2} f^2(X_1, X_2) )^{3/2} $$

I tried to use Hoeffding's result $$ \mathbb E f\left( \sum_{i = 1}^n X_i \right) \le \mathbb E f\left( \sum_{i = 1}^n Y_i \right) $$ ($X_i$ are uniformly at random sampled without replacement, $Y_i$ are uniformly at random sampled with replacement, $f$ is convex and continuous) by combining two elements from set $\mathcal X$ to form a new set: $\{ ( X_i, X_j ) : i \ne j, X_i, X_j \in \mathcal X \}$. However, the sampling process for new set is no longer uniformly at random so I cannot use Hoeffding's result.

Since items are sampled uniformly, this is equivalent to: $$ \left( \dfrac{ \sum_{1 \le i < j < k \le n} f_{ij} f_{ik} f_{jk} }{\binom{n}{3}} \right)^2 \le \left( \dfrac{ \sum_{1 \le i < j \le n} f^2_{ij} } {\binom{n}{2}} \right)^3 $$

For $n = 3$, this is: $$ \left(f_{12} f_{13} f_{23}\right)^2 \le \left( \dfrac{ f_{12}^2 + f_{13}^2 + f_{23}^2}{3} \right)^3 $$ which follows from the inequality between the geometric mean and the root-mean-square: $$ \left(abc\right)^{1/3} \le \sqrt{\dfrac{a^2 + b^2 + c^2}{3}} $$

For $n=4$, this is: $$ \left(\frac{f_{12}f_{13}f_{23}+f_{12}f_{14}f_{24}+f_{13}f_{14}f_{34}+f_{23}f_{24}f_{34}}{4}\right)^2 \leq \left(\frac{f_{12}^2+f_{13}^2+f_{14}^2+f_{23}^2+f_{24}^2+f_{34}^2}{6}\right)^3 $$ which follows from https://artofproblemsolving.com/community/user/12908: \begin{align} \left(abd+ace+bcf+def\right)^2 &= \Big(a(bd+ce)+(bc+de)f\Big)^2 \\ &\le \left(a\sqrt{(b^2+c^2)(d^2+e^2)}+f\sqrt{(b^2+d^2)(c^2+e^2)}\right)^2 \\ &\le \left(\sqrt{(a^2+f^2)\big((b^2+c^2)(d^2+e^2)+(b^2+d^2)(c^2+e^2)\big)}\right)^2 \\ &= (a^2+f^2)(b^2+c^2)(d^2+e^2)+(a^2+f^2)(b^2+d^2)(c^2+e^2)\\ &\le \left(\frac{a^2+f^2+b^2+c^2+d^2+e^2}{3}\right)^3+\left(\frac{a^2+f^2+b^2+d^2+c^2+e^2}{3}\right)^3 \\ &= 16\left(\frac{a^2+b^2+c^2+d^2+e^2+f^2}{6}\right)^3 \end{align}

Answer 1

Let $\lambda_1,\dots,\lambda_n$ be eigenvalues of the symmetric matrix $(f_{ij})$, where $f_{ii}=0$ by definition. They are real, $\sum \lambda_i=0$ and the inequality rewrites as $$ \left(\frac{\sum \lambda_i^3}{n(n-1)(n-2)}\right)^2\leqslant \left(\frac{\sum \lambda_i^2}{n(n-1)}\right)^3, $$ or $(\sum \lambda_i^3)^2\leqslant \frac{(n-2)^2}{n(n-1)}(\sum \lambda_i^2)^3$.

Now fix $\sum \lambda_i^2=S$ and $\sum \lambda_i=0$ and maximize $\sum \lambda_i^3$. When $\sum \lambda_i^3$ is maximal, the gradient vectors $(1,1,\dots,1),2(\lambda_1,\lambda_2,\dots,\lambda_n),3(\lambda_1^2,\lambda_2^2,\dots,\lambda_n^2)$ must be linearly dependent by Lagrange multipliers theorem. In other words, there should exist number $A,B,C$ not all equal to 0 such that $A+B\lambda_i+C\lambda_i^2=0$ for all $i$. Therefore $\lambda$'stake at most 2 different values. Without loss of generality $a+b=n$, $a$ $\lambda$'s are equal to $b$, $b$ $\lambda$'s are equal to $-a$ (for some $a\in \{1,2,\dots,n-1\}$), and the inequality rewrites as $(ab^3-ba^3)^2\leqslant \frac{(n-2)^2}{n(n-1)}(ab^2+ba^2)^3$, or $(b-a)^2\leqslant \frac{(n-2)^2}{n-1}ab$. This is clear from $|b-a|\leqslant n-2$, $ab\geqslant n-1$.