2
$\begingroup$

Let $k$ be an even number. For a $k$-dimensional cube (http://mathworld.wolfram.com/HypercubeGraph.html) $Q_k$, let $G$ be a subgraph of $Q_k$ with $2^{k-1}+s$ vertices, for $1\le s\le 2^{k-1}-1$. I am wondering what is maximum number of edges $G$ can have?

A theorem says average degree of $G$ is at most $v_G\log_2 v_G$, so the number of edges of $G$ is at most $\lfloor\frac{v_G\log_2 v_G}{2}\rfloor$. But is this the best bound? For example when $s=1$, in my mind, to maximize the number of edges on $2^{k-1}+1$ vertices, it should contains a $(k-1)$-dim subcube, say $\{(x_1,\dots,x_{n-1},0):x_i\in\{0,1\}\}$. But then the remaining vertex $(y_1,\dots,y_{n-1},1)$ can have only one edge with the subcube. So this $G$ has only $(k-1)2^{k-2}+1$ edges. But for even $k$, $$\lfloor\frac{v_G\log_2 v_G}{2}\rfloor=\lfloor\frac{(2^{k-1}+1)\log_2 (2^{k-1}+1)}{2}\rfloor\ge \lfloor\frac{(2^{k-1}+1)(k-1)}{2}\rfloor=\frac{(2^{k-1}+1)(k-1)-1}{2}=(k-1)2^{k-2}+\frac{k-2}{2},$$ which is much larger than $(k-1)2^{k-2}+1$ when $k$ is large. Therefore I am asking when $k$ is even and $2^{k-1}+1\le v_G\le 2^{k-1}+2^{k-1}-1$, is the bound $\lfloor\frac{v_G\log_2 v_G}{2}\rfloor$ tight, or is there any other better result?

$\endgroup$
  • $\begingroup$ When two numbers are close to $2^k$, and they only differ by about $k$, I wouldn't say one number is much larger than the other. $\endgroup$ – Gerry Myerson Feb 15 '18 at 21:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.