# Questions tagged [hypercube]

For questions involving cubes in higher dimensions or the hypercube graphs.

**2**

votes

**0**answers

149 views

### A question of Ahlswede and Katona: known lower bounds on $\beta(d,n)$?

Given a set $S\subseteq \{0,1\}^d$ of the Boolean hypercube of dimension $d$, define the average distance of $S$ as
$$
\bar{d}(S) = \frac{1}{\lvert S\rvert^2} \sum_{x,y\in S} d_H(x,y)\tag{1}
$$
where $...

**0**

votes

**0**answers

48 views

### Interesting First-Order Properties of Hypercubes and Grids

Hypercubes:
The $n$-hypercube is the graph $H_n$ whose vertex set $V(H_n)$ consists of all binary string of length $n$, and the edges are pairs of the form $\{w,w'\}$ where $w$ and $w'$ differ in ...

**3**

votes

**0**answers

110 views

### Number of hypercube unfoldings

While writing the code for this answer, I noticed that I not only could calculate the number of unfoldings of the $4$-cube, but also the number of the $n$-cube for more values of $n$. Basically, we ...

**6**

votes

**1**answer

174 views

### Cycles in the hyperoctahedral group (symmetries of the hypercube)

Let $B_n$ be the hyperoctahedral group (the isometries of the $n$-dimensional hypercube). Let $k <n$ and consider the action of $B_n$ on the $k$-dimensional faces of the hypercube.
What can you ...

**2**

votes

**0**answers

48 views

### Hamiltonian cycle polytope for the hypercube graph

Let $Q_n$ denote the $n$ dimensional hypercube graph (i.e., graph formed from the vertices and edges of an n-dimensional hypercube). Denote the set of edges and vertices of $Q_n$ by $E_n$ and $V_n$ ...

**5**

votes

**0**answers

191 views

### Longest simple path through hypercube corners

This is a variation on a previously answered question,
Longest path through hypercube corners.
Here I am seeking the longest simple (non-self-intersecting) path through
the unit hypercube's vertices,
...

**12**

votes

**4**answers

712 views

### Longest path through hypercube corners

Is the longest Hamiltonian path through the $2^d$ unit hypercube vertices known,
where path length is measured by Euclidean distance in $\mathbb{R}^d$?
The unit hypercube spans from $(0,0,\ldots,0)$ ...

**3**

votes

**1**answer

121 views

### Distance relation among points in high-dimensional hypercubes

Let $Q_{4n-1}$ be a unit hypercube of dimension $4n-1$. Has the following statement been proven?
There are $4n$ vertices in $Q_{4n-1}$ such that the distance between each pair of them is $2\sqrt{...

**1**

vote

**1**answer

142 views

### Given a continuous function of many variables, how do I know when this function is equals to zero on all the corners of a unit hypercube?

Given a continuous and deriviable function of many variables, how do I know when this function is equals to zero on all the corners (or vertices) of a unit hypercube, i.e. all points, where each ...

**2**

votes

**0**answers

79 views

### Counting Cycle Vertex Covers on Hypercube

Let $Q_n$ be the $n$-dimensional hypercube graph. How many vertex cycle covers exist on $Q_n$? (Presumably the best we can hope for are upper and lower bounds.) To be clear, a single "vertex cycle ...

**1**

vote

**0**answers

80 views

### Characterizing normal vectors of affinely independent subsets of the hypercube

Suppose we are looking at the hypercube in $\mathbb{R}^n$. I tend to the think of the cube with vertex coordinates 0 or 1, but maybe this is easier for the $\pm1$ cube.
Now suppose we have an affine ...

**0**

votes

**0**answers

140 views

### Is there any result on the homomorphic images of hypercube graphs?

Let $Q_n$ be a hypercube graph and $\phi: Q_n\to G$ a surjective simplicial graph morphism i.e. if $u,v$ are adjacent vertices in $Q_n$ then either $\phi(u)=\phi(v)$ or $\phi(u),\phi(v)$ are adjacent. ...

**0**

votes

**0**answers

80 views

### Commutator subgroup of rotational symmetries of the hypercube

I would like to know which is the commutator subgroup of the group of rotational isometries of the $n$-dimensional cube. The group i am talking about is the subgroup of $\{ \pm 1 \} \wr S_n$ ...

**4**

votes

**2**answers

248 views

### Can we find 3 disjoint directed Hamiltonian cycles in the cube?

Let $D$ be the digraph on $2^d$ vertices with $d2^d$ edges that we obtain by directing each edge of the $d$-dimensional hypercube in both directions.
Can we partition the edges of $D$ into $d$ ...

**4**

votes

**0**answers

323 views

### Hypercube edge-coloring problem

Question: Is there a pairing (a fixed point free involution) of the vertices of the $n$-dimensional cube graph, and a $2$-coloring of its edges such that the number of color changes needed to get from ...

**8**

votes

**1**answer

132 views

### Tilting the $d$-cube to vertically separate its vertices

Let $C_d$ be a unit edge-length cube in $d$ dimensions.
I would like to orient it ("tilt" it) so that the vertical (last) coordinates
of its $2^d$ vertices are maximally separated, in the sense
that ...

**10**

votes

**1**answer

308 views

### Are there non-trivial graphs that uniquely embed to hypercubes?

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

**10**

votes

**1**answer

382 views

### What's the volume of $\{x\in[0,1]^n|\sum x_i\le t\}$ for real $t$?

EDIT: Thanks for your answers and comments. There is indeed a classical easy formula, given by Pietro Majer (with a simple nice proof) in his answer below.
Given $x\in\mathbb{R}^n$, $x_i$ denotes its ...

**0**

votes

**0**answers

130 views

### Symmetries higher dimensional cube fixing subcubes

Which is the group of rotational isometries of an $n$ dimensional hypercube fixing an $m$ dimensional element (an $m$ dimensional subcube)? I know for example that it is $A_n$ for $m=0$ (symmetries ...

**13**

votes

**1**answer

650 views

### Maximum number of vectors in a hypercube satisfying given conditions

$\mathcal{C}$ is a collection of binary vectors of length $n$, i.e. $\mathcal{C}\subseteq\{0,1\}^n$. For arbitrary $x,y,z\in\mathcal{C}$ and $x\neq z$, $y\neq z$, there always holds that the Euclidean ...

**14**

votes

**0**answers

367 views

### Monotone embedding of complete binary tree in hypercube

Embedding different graphs, especially binary trees, in the hypercube has a huge literature. However, I could not find anything if we restrict the embedding to be monotone. So I would like to ...

**2**

votes

**3**answers

242 views

### Inequality involving size of nodes & min degree of graph

Context:
http://www.sciencedirect.com/science/article/pii/S0019995882904776
Lemma 1 on 3rd page.
Question excerpted / rewritten as follows:
Let $G=(V,E)$ be the $n$-dimensional hypercube. That is $...