MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 0 down vote accepted

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...

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.