Questions tagged [hypercube]
For questions involving cubes in higher dimensions or the hypercube graphs.
36
questions
2
votes
2
answers
130
views
Is $F(F(A)) = A$ for every k-hypercube where k is odd?
Suppose we have a k-hypercube $(Q_k)$ where $k$ is an odd integer.
Define $F(A)$ for $A \subseteq V$ as the set of all vertices such that has odd number of edges to the set $A$.
Is it true that $F(F(A)...
- 105
1
vote
0
answers
72
views
Keller's cubing conjecture but with arbitrary cubes of side $1$
These days I have been reading about Keller's cube tyling conjecture, which asks if in any covering of $\mathbb{R}^n$ by translates of $[0,1]^n$ with disjoint interiors there are two cubes sharing one ...
- 7,164
2
votes
1
answer
64
views
Bounded positioning of hypercubes
I have the following question:
Let be (C_n) a sequence of m-dimensional hypercubes such that the series over the volumes of this cubes converges. I assume that it's possible to place those cubes in ...
0
votes
0
answers
64
views
Intersections of a hypercube with a plane
Let a hypercube be given in $\mathbb{R}^n$ and a plane passing through its center. Are there any works in which the possible number of cube vertices through which this plane passes was investigated? ...
- 1
4
votes
0
answers
176
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 ...
- 3,601
25
votes
1
answer
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 ...
- 147k
12
votes
3
answers
339
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 ...
- 223
2
votes
1
answer
208
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. ...
- 49
5
votes
0
answers
72
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 ...
- 11.4k
10
votes
2
answers
338
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}.$$
...
- 185
1
vote
0
answers
119
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 ...
- 11
2
votes
1
answer
124
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 ...
- 177
4
votes
0
answers
156
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 ...
- 143
5
votes
1
answer
252
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 ...
- 53
4
votes
1
answer
156
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?
...
- 13.2k
3
votes
1
answer
343
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 $...
- 1,282
25
votes
1
answer
2k
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 ...
- 10.4k
6
votes
1
answer
285
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 ...
- 61
3
votes
0
answers
140
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$ ...
- 373
5
votes
0
answers
428
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,
...
- 147k
12
votes
4
answers
2k
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)$ ...
- 147k
3
votes
1
answer
144
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{...
- 4,125
1
vote
1
answer
184
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
145
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 ...
- 3,650
1
vote
0
answers
91
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 ...
- 908
0
votes
0
answers
185
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. ...
- 803
0
votes
0
answers
104
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
326
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$ ...
- 18k
4
votes
0
answers
545
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 ...
- 2,994
18
votes
3
answers
393
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 ...
- 147k
10
votes
1
answer
375
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 ...
- 18k
10
votes
1
answer
494
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 ...
- 1,787
0
votes
0
answers
145
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
724
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 ...
- 147
14
votes
0
answers
393
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 ...
- 18k
2
votes
3
answers
287
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 $...
- 31