The $n$-dimensional hypercube is the graph formed by $0$-$1$ sequences of length $n$ where two vertices are adjacent if they differ at only one place.
The weight of a sequence is the number of $1$'s in it.
For a (connected) subgraph of a hypercube we say that its *level-vector* is $(n\_1,\ldots,n\_k)$ if the number of its vertices with minimum weight is $n\_1$, with minimum $+1$ weight is $n\_2$ etc.
In other words, $n\_1,\ldots,n\_k$ is the number of vertices on the non-empty (adjacent) levels of the hypercube.


We say that a graph $G$ *level-uniquely embeds to hypercubes* if the level-vector of every induced subgraph of any hypercube that is isomorphic to $G$ is the same (and there is at least one hypercube that contains an induced subgraph that is isomorphic to $G$).



> 
> 
> > 
> > Is there a graph that level-uniquely embeds to hypercubes but is not a hypercube itself?
> > 
> > 
> > 
> 
> 
> 


**Update 2014.12.28** This has been answered in the negative by Flo, see his answer below.


In fact, for my problem a slightly weaker condition would also suffice. Namely, I am also interested in graphs for which there is an $\alpha\ne -1$ such that for the level-vector $(n\_1,\ldots,n\_k)$ of every induced subgraph of any hypercube that is isomorphic to the graph it holds that $\alpha$ is the root of the *level-polynomial* $\sum n\_ix^i$.



> 
> 
> > 
> > Is there a graph and an $\alpha\ne -1$ such that $\alpha$ is the root of every level-polynomial?
> > 
> > 
> > 
> 
> 
> 


My motivation is that if there existed such a graph on a power of $2$ vertices, then I think it would give an example to the question posed [here](http://www.iwoca.org/problems/Griggs2014.pdf) using [this](https://mathoverflow.net/a/51822/955) method.
I've found some nice induced subhypercubes [here](http://www.emis.ams.org/journals/JACO/Volume2_1/k312688v37355582.fulltext.pdf), but they were too big for me to verify anything.




---


***The text below is an exposition of the question by Wlodzimierz, edited by me***


Let $\ \mathbb B:=\{0\ 1\}.\ $ Let $\ \mathbb B^n\ $ be the $n$-cube. The elements of the $n$-cube are called vertices. The weight $\ \sum x\ $ of a vertex $\ x:=(x\_1\ldots x\_n)\in\mathbb B^n\ $ is defined as the sum of the coordinates, $\ \sum x := \sum\_{k=1}^n x\_k.\ $ Given an arbitrary set $\ A\subseteq\mathbb B^n,\ $ define the weigram $\ w\_A:\mathbb Z\rightarrow\mathbb Z,\ $ where $\ w\_A(k)\ $ is the number of vertices $\ x\in A\ $ of weight $\ k,\ $ for every $\ k=0\ldots n;\ $ also $\ w\_A(k):=0\ $ whenever $\ k<0\ $ or $\ k>n.\ $


Consider arbitrary $\ A\ \subseteq \mathbb B^n, \ B\ \subseteq \mathbb B^m. $ We say that $\ B\ $ is a weight-shift of $\ A\ $ $\ \Leftarrow:\Rightarrow\ \exists\_{d\in\mathbb Z}\forall\_{k\in\mathbb Z}\ w\_B(k) = w\_A(k+d)$.


Now let's introduce the graph structure in the $n$-cube. Its edges are pairs $\ \{a\ b\}\subseteq\mathbb B^n\ $ such that $\ a\ b\ $ have exactly one coordinate different (i.e. $\ \sum |a-b| = 1$). Every $\ A\subseteq\mathbb B^n\ $ is considered to be a graph induced by the $n$-cube graph. Two subsets of the $n$-cube are considered to be isomorphic $\ \Leftarrow:\Rightarrow\ $ they are isomorphic as graphs.



> 
> **QUESTIONS** (consider implicitly the versions for connected graphs too, or especially for the connected graphs):
> 
> 
> 1. Is there set $A\ne \emptyset, \mathbb B^n$, such that every $\ B\subseteq \mathbb B^m\ $ which is isomorphic to $\ A\ $ is a weight-shift of $\ A?\ $
> 2. Can you describe all sets $\ A\ $ as above?
> 3. Questions related to the roots of the polynomials $\ \sum\_k w\_A(k)\cdot t^k\ $ (see above the part one).
> 
> 
> 



Are there non-trivial graphs that uniquely embed to hypercubes?
For your first question, I believe that only hypercubes can embed uniquely.


First note that $G$ has to be $n\_2$-regular, and $n\_1=1$: take any embedding, and use coordinate flips so that your favorite vertex $v$ of $G$ is embedded in $(0,0,0,...,0)$. Then $n\_1=1$, and all $n\_2$ vertices of weight $1$ are neighbors of $v$.


Now let $H$ be the smallest hypercube $G$ embeds uniquely into, say $|H|=2^n$. If $G$ is $n$-regular, then $G=H$. Otherwise, there is some embedding with $v=(0,...,0)$ and $(1,0,...0)\notin V(G)$. Switch the first coordinate on all vertices in $G$, giving a new embedding with minimum weight $1$. As $G$ embeds uniquely, every vertex of $G$ must have gained $1$ in weight, so all vertices had first coordinate $0$. But then $G$ embeds uniquely in the smaller hypercube, contradiction.


