Tomas Feder, Carlos Subi

We conjecture that for every perfect matching $M$ of the $d$-dimensional

$n$-vertex hypercube, $d\geq 2$, there exists a second perfect matching $M'$

such that the union of $M$ and $M'$ forms a Hamiltonian circuit of the

$d$-dimensional hypercube. We prove this conjecture in the case where there are

two dimensions ...
more >>>

Tomas Feder, Carlos Subi

It has been shown that for every perfect matching $M$ of the $d$-dimensional

$n$-vertex hypercube, $d\geq 2, n=2^d$, there exists a second perfect matching

$M'$ such that the union of $M$ and $M'$ forms a Hamiltonian circuit of the

$d$-dimensional hypercube. We prove a generalization of a special case of ...
more >>>

Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff

Given a directed graph $G = (V,E)$ and an integer $k \geq 1$, a $k$-transitive-closure-spanner ($k$-TC-spanner) of $G$ is a directed graph $H = (V, E_H)$ that has (1) the same transitive-closure as $G$ and (2) diameter at most $k$. Transitive-closure spanners were introduced in \cite{tc-spanners-soda} as a common abstraction ... more >>>

David GarcĂa Soriano, Arie Matsliah, Sourav Chakraborty, Jop Briet

We study the problem of monotonicity testing over the hypercube. As

previously observed in several works, a positive answer to a natural question about routing

properties of the hypercube network would imply the existence of efficient

monotonicity testers. In particular, if any $\ell$ disjoint source-sink pairs

on the directed hypercube ...
more >>>

Petr Savicky

A Boolean function is called vertex-transitive, if the partition of the Boolean cube into the preimage of 0 and the preimage of 1 is invariant under a vertex-transitive group of isometric transformations of the Boolean cube. Several constructions of vertex-transitive functions and some of their properties are presented.