10
$\begingroup$

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 using this method. I've found some nice induced subhypercubes here, 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).
$\endgroup$
  • $\begingroup$ @d -- References were fine all the time. I got confused by the code view, silly me. $\endgroup$ – Włodzimierz Holsztyński Dec 24 '14 at 14:03
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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