The set of vertices of $Q(d,n)$ is $\{0,1,\ldots,n-1\}^d$ and every edge is formed by all vertices having $d-1$ coordinates fixed and the last one getting all possible values (so it has $dn^{d-1}$ edges).


I'm trying to prove that $Q(n,n)$ has the following property: if $S$ is some subset of its edges and $U$ is their union, then $|S|\leq\frac{|U|\log|U|}{n\log n}$. I'm sure that's true, extreme cases (when the inequality becomes an equality) being those when $U$ is a hypercube of lesser dimension and $S$ consists of all edges in $U$, but I don't know how to approach the proof. Could you give any hints?



Property of cube hypergraph Q(n,n)
**1.** First of all, you can ``shake down'' all your edges along each direction. That is --- choose any direction (say, vertical) and consider all the edges in $S$ of all other directions. Then simultaneously drop all of them as low as possible (preserving the condition that they are distinct). It is easy to see that on each vertical segment, the number of covered points does not increase (in fact, it becomes equal to a maximal number of parallel non-vertical edges intersecting this segment, if this segment itself was not in $S$). So, $|U|$ does not increase as well.


**2.** Thus, we may suppose that our set $S$ is shaken down in all directions. Now we can prove your claim by the induction on $d$. We may assume that the base of all logarithms is $n$, hence the inequality looks like $n|S|\leq |U|\log |U|$.


For $d=0$, the claim is obvious. Now assume that $d>0$, and again some of the axes is vertical. Divide all the edges in $S$ into parts $S\_0,\dots,S\_n$ as follows: for $i\leq n-1$, $S\_i$ is the set of all non-vertical segments in $S$ having $i$ as their vertical coordinate, and $S\_n$ is the set of all vertical segments. Next, let $U=U\_0\sqcup \dots\sqcup U\_{n-1}$, where $U\_i$ is the set of all points in $U$ with $i$ as their vertical coordinate. Denote $|U|=u$, $|U\_i|=u\_i$. Due to the shattering, we have $u\_1\geq \dots\geq u\_n$.


By the induction hypothesis, we have $n|S\_i|\leq u\_i\log u\_i$ for $i<n$ whenever $u\_i>0$; next, $|S\_n|\leq u\_{n-1}$. 


  



*Case 1.* Assume that $u\_{n-1}=0$, and let $k\leq n-2$ be the maximal index such that $u\_k\geq 1$. Then
$$
 n|S|=\sum\_{i=0}^{k}n|S\_i|\leq \sum\_{i=0}^{k}u\_i\log u\_i
 \leq u\log u,
$$
with the equality achieved only if $k=1$.


  



*Case 2.* Assume that $u\_{n-1}>0$. Then
$$
 n|S|=\sum\_{i=0}^{n-1}n|S\_i|\leq \sum\_{i=0}^{n-1}u\_i\log u\_i+nu\_{n-1}.
$$
So we are left to prove that
$$
 nu\_{n-1}+\sum\_i u\_i\log u\_i\leq u\log u.
 \qquad\qquad (\*)
$$
This happens to be a bit messy. Let us fix $u=\sum u\_i$ and change the values of $u\_i$'s. Since the function $x\log x$ is convex on $[1,+\infty)$, we may simultaneously change $u\_i\to u\_n$ for $i>0$, $u\_0\to u-(n-1)u\_{n-1}$, increasing the left-hand part of $(\*)$. Hence, denoting $x=u\_{n-1}$, $y=u\_0$, we need to prove that
$$
 nx+(n-1)x\log x+y\log y\leq ((n-1)x+y)\log((n-1)x+y),
$$
or
$$
 nx\leq (n-1)x\log\left(n-1+\frac yx\right)+y\log\left(1+\frac{(n-1)x}y\right),
$$
or, denoting $1+c=y/x$ and dividing by $x$,
$$
 n\leq (n-1)\log(n+c)+(1+c)\log(n+c)-(1+c)\log(1+c).
$$
In other words, we need
$$
 n\log n-1\log 1\leq (n+c)\log(n+c)-(1+c)\log(1+c),
$$
which follows again from the convexity of $x\log x$.


Perhaps, the last part can be simplified...


