<s>[INST] Expectation inequality for sampling without replacement 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}
 [/INST] 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$.
</s>