How many edges can a t-vertex cubical graph have?

Question

The $n$-dimensional hypercube $Q_n$ is the graph whose vertex set is $\{0, 1\}^n$ and whose edge set is the set of pairs that differ in exactly one coordinate. A graph is called cubical if it is a subgraph of $Q_n$ for some $n$. We know that $|V(Q_n)|=2^n$ and $|E(Q_n)|=n 2^{n-1}$, so $|E(Q_n)|=\frac{1}{2}|V(Q_n)|\log_2 |V(Q_n)|$. Graham [On primitive graphs and optimal vertex assignments. Ann. New York Acad. Sci. 175 (1970), 170--186] showed that a $t$-vertex cubical graph can have at most $(1+o(1))\frac{1}{2}t\log_2 t$ edges. My question is: can a $2^{n}$-vertex cubical graph have more than $n2^{n-1}$ edges? In general, for $2^{n-1}< t \leq 2^{n}$, can a $t$-vertex cubical graph have more edges than the subgraph of $Q_n$ induced by any $t$ vertices?

Comment. I have read the paper of Graham again, and I realized that he in fact proved that a $t$-vertex cubical graph can have at most $W(t-1)$ edges, where $W(t-1)=w(1)+\ldots+w(t-1)$ and $w(i)$ is the number of 1's in the binary expansion of $i$. This upper bound can be achieved by some $t$ vertices in $Q_n$ for $2^{n-1}< t \leq 2^{n}$. So my question is solved. Fedor Petrov gave a very nice proof of the statement that a $t$-vertex cubical graph can have at most $\frac{1}{2}t\log_2 t$ edges. Thanks a lot!

Answer 1

Let me try to prove that for every integer $t>0$ the number of edges of a $t$-vertex cubical graph has at most $\frac12 t\log_2t$ edges.

This is true for $t=1$. So assume (by induction) that $t>1$ and it is proved for smaller number of vertices. Without loss of generality, the vertex set of our graph contains the elements of $\{0,1\}^n$ with last coordinates equal to 0 and equal to 1. So, we may write $t=a+b$ where $a\geqslant b>0$ and $a$, $b$ denote the number of vertices with last coordinates equal to 0 and 1. By induction hypothesis, the number of edges does not exceed $$\frac12a\log_2a+\frac12b\log_2b+b,$$ where the last summand corresponds to edges between vertices which differ in the last coordinate. Thus, it suffices to prove the inequality $$\label{1} \frac12a\log_2a+\frac12b\log_2b+b\leqslant \frac12(a+b)\log_2(a+b).\tag{1} $$ Denoting $a=xb$, $x\geqslant 1$, \eqref{1} reads as $$f(x):=(x+1)\log(x+1)-x\log x\geqslant 2\log 2=f(1).\tag{2}\label{2}$$ We have $f'(x)=\log(x+1)-\log x\geqslant 0$, fo $f$ increases that yields \eqref{2}.