# Questions tagged [hypercube]

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

32 questions
Filter by
Sorted by
Tagged with
151 views

### Min max of a quadratic form of plus-minus ones

Does the following limit exist? $$\lim_{n \to \infty}\, n^{-3/2} \min_{a_{ij}=\pm 1}\max_{x_{j}=\pm 1}\left|\sum_{1\leq i <j \leq n} a_{ij}x_{i}x_{j} \right|$$ There is no any significant ...
1k views

### Which unfoldings of the $d$-dimensional hypercube tile $(d{-}1)$-space?

A six year old question, Which unfoldings of the hypercube tile $3$-space?, has just been answered by Moritz Firsching: All $261$ unfoldings tile space! So now we know: For $d=2$, the unfolding of ...
302 views

### Probability of $\ell_1$-norms of vertices of the rotated Hamming cube

Let $O$ be a $d$-dimensional rotation matrix (i.e., it has real entries and $OO^T = O^TO = I$). Let $\mathbf{x}$ be a uniformly random bitstring of length $d$, i.e., $\mathbf{x} \sim U(\{0,1\}^d)$. In ...
163 views

### How to fold a tesseract from L-unfolding? [closed]

I came across an image, that show really simple unfold of 4-dim cube. https://arxiv.org/pdf/1512.02086.pdf here at #2.1, and 120 here https://page.mi.fu-berlin.de/moritz/mo/198722/unfoldings.html. ...
66 views

### Which polytopes can be deformed while keeping their edge-lengths?

Let $P\subset\Bbb R^d$ be a convex polytope (a convex hull of finitely many points). Lets call it flexible, if it can be continuously deformed while keeping its combinatorial type, and keeping its ...
319 views

### Closed walks on an $n$-cube and alternating permutations

Let $w(n,l)$ denote the number of closed walks of length $2l$ from a given vertex of the $n$-cube. Then, it is well-known that $$\cosh^n(x)=\sum_{l=0}^{\infty}\frac{w(n,l)}{(2l)!}x^{2l}.$$ ...
1 vote
98 views

### Regular triangulation of hypercube

I have started studying regular subdivisions of the $n$-cube, and came across the following post: Regularity of Delaunay triangulation of a hypercube. My question is whether the "standard ...
94 views

### Maximal area/volume of (d-1)-dimensional object in d-dimensional hypercube

What is the largest area/volume of any $(d-1)$-dimensional flat object that fits into the $d$-dimensional unit hypercube? For instance, for $d=2$, the answer is $\sqrt 2$, as this is the length of the ...
121 views

### Are mixed discriminants and hyper-determinants the same thing?

Premise Hello, I'm trying to learn more about hyperdeterminants, but as I'm sifting through the literature I'm finding more and more papers on Mixed discriminant and I find their definitions extremely ...
230 views

### Random walk on the hypercube with deleted edges

Let $G$ be the $n$-dimensional boolean hypercube, i.e. the graph on $\{0,1\}^n$ where two vertices are adjacent iff they differ on exactly one coordinate. Consider a graph $G'$ obtained by deleting a ...
154 views

### Complementing the red and blue boolean cube?

Given a boolean $0/1$ cube in $n$ dimensions with $2^{n-1}$ red and $2^{n-1}$ blue points can we complement the cube (blue becomes red and vice versa) in $\operatorname{poly}(n)$ transformations? ...
327 views

1 vote
177 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 ...
132 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
89 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 ...
181 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. ...
103 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$ ...
321 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$ ...
532 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 ...
383 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 ...
353 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 ...
479 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 ...
144 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 ...
713 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 ...
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 \$...