Skip to main content

Questions tagged [hypercube]

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

Filter by
Sorted by
Tagged with
3 votes
1 answer
192 views

Some questions about induced subgraphs of the directed hypercube graph

Let $Q^n$ be the hypercube graph in $n$ dimensions. Hao Huang famously showed that any induced subgraph on more than $2^{n-1}$ must have maximum degree $ \geq \sqrt{n}$. It is also known that this ...
Agile_Eagle's user avatar
2 votes
0 answers
112 views

Hypercube of chain complexes as functor from (Δ^1 )^n to ∞-category of chain complexes

A hypercube of chain complexes consists of $\mathbb{Z}$-graded vector spaces $C_\epsilon$ for $\epsilon\in\{0,1\}^n$ and maps $D_{\epsilon,\epsilon^\prime}:C_{\epsilon}\to C_{\epsilon^\prime}$ for $\...
Faniel's user avatar
  • 653
1 vote
0 answers
42 views

Complexity of the TSP for hypercube graphs

Question: what is known about the complexity of finding the Hamilton cycle of minimum weight in graphs that resemble hypercubes with weighted edges?
Manfred Weis's user avatar
  • 12.7k
3 votes
0 answers
56 views

Concentration for Hamming balls

It is well known that Lipschitz functions on the Boolean $n$-cube endowed with the Hamming metric satisfy concentration properties. Specifically, most of their values lie in a range of width $O(\sqrt ...
alesia's user avatar
  • 2,582
1 vote
0 answers
56 views

Maximize trace of precision matrix

Let Q be the uniform distribution over the hypercube $\{1, -1\}^{d}$. Let P be any distribution that has support including the hypercube. Define $\Sigma=\mathbb{E}_{x \sim P}[x x^\top]$. We'd like to ...
Wuchen's user avatar
  • 505
1 vote
0 answers
99 views

Hypercube and affine space [closed]

We have an affine subspace $A$ of dimension $d_{A}$ and a hypercube $C$ of dimension $d_{C}$ ($d_{C}=n$), with $d_{A}\lt d_{C}$ and both belong to $\Re ^{n}$. Each face of dimension $d_{C}-1$ of $C$ ...
Mario Giambarioli's user avatar
2 votes
2 answers
146 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)...
Nima Aryan's user avatar
1 vote
0 answers
74 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 ...
Saúl RM's user avatar
  • 8,256
2 votes
1 answer
76 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 ...
Maxim Glyzhev's user avatar
4 votes
0 answers
188 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 ...
Paata Ivanishvili's user avatar
24 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 ...
Joseph O'Rourke's user avatar
12 votes
3 answers
367 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 ...
arriopolis's user avatar
2 votes
1 answer
276 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. ...
Ivan Molotov's user avatar
5 votes
0 answers
88 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 ...
M. Winter's user avatar
  • 12.6k
11 votes
2 answers
357 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}.$$ ...
bryanjaeho's user avatar
1 vote
0 answers
153 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 ...
KTree's user avatar
  • 11
2 votes
1 answer
135 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 ...
Bodo Manthey's user avatar
4 votes
0 answers
179 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 ...
Luca Cappelletti's user avatar
5 votes
1 answer
286 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 ...
RandomWalker's user avatar
4 votes
1 answer
166 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? ...
Turbo's user avatar
  • 13.7k
3 votes
1 answer
354 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 $...
Clement C.'s user avatar
  • 1,342
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 ...
Moritz Firsching's user avatar
6 votes
1 answer
301 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 ...
user124105's user avatar
3 votes
0 answers
143 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$ ...
Ozzy's user avatar
  • 383
5 votes
0 answers
487 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, ...
Joseph O'Rourke's user avatar
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)$ ...
Joseph O'Rourke's user avatar
3 votes
1 answer
156 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{...
C.F.G's user avatar
  • 4,165
1 vote
1 answer
192 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 ...
Farewell Stack Exchange's user avatar
3 votes
1 answer
198 views
+100

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 ...
Bill Bradley's user avatar
  • 3,819
1 vote
0 answers
99 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 ...
batconjurer's user avatar
0 votes
0 answers
198 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. ...
Reza Rezazadegan's user avatar
0 votes
0 answers
107 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$ ...
quelramodellago's user avatar
4 votes
2 answers
337 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$ ...
domotorp's user avatar
  • 18.4k
4 votes
0 answers
572 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 ...
Daniel Soltész's user avatar
18 votes
3 answers
402 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 ...
Joseph O'Rourke's user avatar
10 votes
1 answer
396 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 ...
domotorp's user avatar
  • 18.4k
10 votes
1 answer
519 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 ...
Mathieu Baillif's user avatar
0 votes
0 answers
147 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 ...
Giovanni_M's user avatar
13 votes
1 answer
748 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 ...
SGC's user avatar
  • 147
14 votes
0 answers
412 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 ...
domotorp's user avatar
  • 18.4k
2 votes
3 answers
344 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 $...
circuits's user avatar