If a $3$-uniform hypergraph has ${x \choose 3}$ edges, then it has at most ${x \choose 4}$ copies of $K^3_4$

Question

Show that if a 3-uniform hypergraph has ${x \choose 3}$ edges (for some positive real number $x$), then it has at most ${x \choose 4}$ copies of $K^3_4$ (the complete $3$-uniform hypergraph on $4$ vertices). Show that the bound is tight for every integer $x \geq 3$.

Answer 1

Intuitively this is easy to see: with a fixed number of hyperedges, you will maximize the number of complete subgraphs when the hyperedges share as many vertices as possible. So in your case: consider the complete 3-uniform hypergraph on $x$ vertices. It has $\binom{x}{3}$ hyperedges (as requested), and contains $\binom{x}{4}$ copies of $K_4^3$. This proves that the upper bound is tight.

Answer 2

This is a special case of the Kruskal–Katona theorem.

For a set $S$, let $\binom Sk$ denote all the $k$-element subsets of $S$. Lovász's simplified formulation of the Kruskal–Katona theorem says the following.

For any $n$ and $k$, take any $\mathcal F \subseteq \binom{[n]}{k}$ with $|\mathcal F| = \binom xk$. (Here, $x$ can be any real number, so any $|\mathcal F|$ can be expressed as $\binom xk$ for some $x$.) Let the shadow $\Delta(\mathcal F)$ be defined as $\bigcup_{A \in \mathcal F} \binom{A}{k-1}$. Then $|\Delta(\mathcal F)| \ge \binom{x}{k-1}$.

In this case, let $k=4$ and let $\mathcal F$ be the set of all $4$-element sets that induce a copy of $K_4^3$ in the hypergraph. In this case, the shadow $\Delta(\mathcal F)$ is a subset of the edge set of the hypergraph (there may also be edges not part of any $K_4^3$). The statement we want to show is just the contrapositive of what Kruskal–Katona tells us.