A combinatorial approach for Keller's conjecture

The statement, that in a tiling by translates of ann-dimensional cube there are two cubes having common (n-1)-dimensional faces, is known as Keller's conjecture. We shall prove that there is a counterexample for this conjecture if and only if the following graphs _n has a 2 ⁿ size clique. The 4 ⁿ vertices of _n aren-tuples of integers 0, 1, 2, and 3. A pair of thesen-tuples are adjacent if there is a position at which the difference of the corresponding components is 2 modulo 4 and if there is a further position at which the corresponding components are different. We will give the size of the maximal cliques of _n forn5.     

Non-periodic Tilings of ? n by Crosses

An n-dimensional cross consists of 2n+1 unit cubes: the “central” cube and reflections in all its faces. A tiling by crosses is called a Z-tiling if each cross is centered at a point with integer coordinates. Periodic tilings of ℝ ⁿ by crosses have been constructed by several authors for all n∈N. No non-periodic tiling of ℝ ⁿ by crosses has been found so far. We prove that if 2n+1 is not a prime, then the total number of non-periodic Z-tilings of ℝ ⁿ by crosses is 2^à₀2^{\aleph _{0}} while the total number of periodic Z-tilings is only ℵ₀. In a sharp contrast to this result we show that any two tilings of ℝ ⁿ ,n=2,3, by crosses are congruent. We conjecture that this is the case not only for n=2,3, but for all n where 2n+1 is a prime.     

The cardinality of the separated vertex set of a multidimensional cube

An n-dimensional cube and the sphere inscribed into it are considered. The conjecture of A. Ben-Tal, A. Nemirovski, and C. Roos states that each tangent hyperplane to the sphere strictly separates not more than 2 ⁿ⁻² cube vertices. In this paper this conjecture is proved for n ≤ 6. New examples of hyperplanes separating exactly 2 ⁿ⁻² cube vertices are constructed for any n. It is proved that hyperplanes orthogonal to radius vectors of cube vertices separate less than 2 ⁿ⁻² cube vertices for n ≥ 3.     

Tiling R 5 by Crosses

An n-dimensional cross comprises 2n+1 unit cubes: the center cube and reflections in all its faces. It is well known that there is a tiling of R ⁿ by crosses for all n. AlBdaiwi and the first author proved that if 2n+1 is not a prime then there are $2^{\aleph_{0}}$ non-congruent regular (= face-to-face) tilings of R ⁿ by crosses, while there is a unique tiling of R ⁿ by crosses for n=2,3. They conjectured that this is always the case if 2n+1 is a prime. To support the conjecture we prove in this paper that also for R ⁵ there is a unique regular, and no non-regular, tiling by crosses. So there is a unique tiling of R ³ by crosses, there are $2^{\aleph_{0}}$ tilings of R ⁴, but for R ⁵ there is again only one tiling by crosses. We guess that this result goes against our intuition that suggests ‘the higher the dimension of the space, the more freedom we get’.     

A reduction of lattice tiling by translates of a cubical cluster

A cluster is the union of a finite number of cubes from the standard partition ofn-dimensional Euclidean space into unit cubes. If there is lattice tiling by translates of a cluster, then must there be a lattice tiling by translates of the cluster in which the translation vectors have only integer coordinates? In this article we prove that if the interior of the cluster is connected and the dimension is at most three, then the answer is affirmative.     

Cube Polynomial of Fibonacci and Lucas Cubes

The cube polynomial of a graph is the counting polynomial for the number of induced k-dimensional hypercubes (k≥0). We determine the cube polynomial of Fibonacci cubes and Lucas cubes, as well as the generating functions for the sequences of these cubes. Several explicit formulas for the coefficients of these polynomials are obtained, in particular they can be expressed with convolved Fibonacci numbers. Zeros of the studied cube polynomials are explicitly determined. Consequently, the coefficients sequences of cube polynomials of Fibonacci and Lucas cubes are unimodal.     

Decomposition of complete graphs into 5‐cubes

Necessary conditions for the complete graph on n vertices to have a decomposition into 5‐cubes are that 5 divides n ? 1 and 80 divides n(n ? 1)/2. These are known to be sufficient when n is odd. We prove them also sufficient for n even, thus completing the spectrum problem for the 5‐cube and lending further weight to a long‐standing conjecture of Kotzig. © 2005 Wiley Periodicals, Inc. J Combin Designs 14: 159–166, 2006     

The View-Obstruction Problem for 5-Dimensional Cubes

 The view-obstruction problem for the n-dimensional cube is equivalent to the conjecture that for any n positive integers there is a real number x such that each (here denotes the distance from y to the nearest integer). This conjecture has been previously solved for . In this paper we prove that when we can find x which gives each ; this is the first improvement over the easy result . Received 5 August 1997; in revised form 19 January 1998     

Recursive fault-tolerance of Fibonacci cube in hypercubes

Fibonacci cube is a subgraph of hypercube induced on vertices without two consecutive 1's. If we remove from Fibonacci cube the vertices with 1 both in the first and the last position, we obtain Lucas cube. We consider the problem of determining the minimum number of vertices in n-dimensional hypercube whose removal leaves no subgraph isomorphic to m-dimensional Fibonacci cube. The exact values for small m are given and several recursive bounds are established using the symmetry property of Lucas cubes and the technique of labeling. The relation to the problem of subcube fault-tolerance in hypercube is also shown.     

On the Existence of Completely Saturated Packings and Completely Reduced Coverings

We prove the following conjecture of G. Fejes Toth, G. Kuperberg, and W.Kuperberg: every body K in either n-dimensional Euclidean or n-dimensional hyperbolic space admits a completely saturated packing and a completely reduced covering. Also we prove the following counterintuitive result: for every >0, there is a body K in hyperbolic n-space which admits a completely saturated packing with density less than but which also admits a tiling.     

A Cube Tiling of Dimension Eight with No Facesharing

Abstract. A cube tiling of eight-dimensional space in which no pair of cubes share a complete common seven-dimensional face is constructed. Together with a result of Perron, this shows that the first dimension in which such a tiling can exist is seven or eight.     

A Cube Tiling of Dimension Eight with No Facesharing

   Abstract. A cube tiling of eight-dimensional space in which no pair of cubes share a complete common seven-dimensional face is constructed. Together with a result of Perron, this shows that the first dimension in which such a tiling can exist is seven or eight.     

Homological Pisot substitutions and exact regularity

We consider one-dimensional substitution tiling spaces where the dilatation (stretching factor) is a degree d Pisot number, and the first rational Čech cohomology is d-dimensional. We construct examples of such “homological Pisot” substitutions whose tiling flows do not have pure discrete spectra. These examples are not unimodular, and we conjecture that the coincidence rank must always divide a power of the norm of the dilatation. To support this conjecture, we show that homological Pisot substitutions exhibit an Exact Regularity Property (ERP), in which the number of occurrences of a patch for a return length is governed strictly by the length. The ERP puts strong constraints on the measure of any cylinder set in the corresponding tiling space.     

Integration over a simplex,truncated cubes,and Eulerian numbers

Summary A method of integrating a function over a simplex is described in which (i) the simplex is first transformed into a right-angled isosceles simplex; (ii) this simplex is dissected into small cubes and truncated cubes; (iii) the integration over the truncated cubes is performed by the centroid method or by Stroud's method, and this requires the use of formulae for the moments of a truncated cube. These formulae are developed and are expressed in terms of Eulerian numbers. In the special case when the truncated cube is itself a right-angled isoceles simplex a new algorithm is given, depending on the discrete Fourier transform, for calculating the moments as polynomials inn wheren is the dimensionality.     

Clique matchings in the <Emphasis Type="Italic">k</Emphasis>-ary <Emphasis Type="Italic">n</Emphasis>-dimensional cube

A clique matching in the k-ary n-dimensional cube (hypercube) is a collection of disjoint one-dimensional faces. A clique matching is called perfect if it covers all vertices of the hypercube. We show that the number of perfect clique matchings in the k-ary n-dimensional cube can be expressed as the k-dimensional permanent of the adjacency array of some hypergraph. We calculate the order of the logarithm of the number of perfect clique matchings in the k-ary n-dimensional cube for an arbitrary positive integer k as n→∞.     

Enumerating Cube Tilings

Cube tilings formed by $n$ -dimensional $4\mathbb Z ^n$ -periodic hypercubes with side $2$ and integer coordinates are considered here. By representing the problem of finding such cube tilings within the framework of exact cover and using canonical augmentation, pairwise nonisomorphic 5-dimensional cube tilings are exhaustively enumerated in a constructive manner. There are 899,710,227 isomorphism classes of such tilings, and the total number of tilings is 638,560,878,292,512. It is further shown that starting from a 5-dimensional cube tiling and using a sequence of switching operations, it is possible to generate any other cube tiling.     

Maximum Matchings in the n-Dimensional Cube

The problem of efficient computation of maximum matchings in the n-dimensional cube, which is applied in coding theory, is solved. For an odd n, such a matching can be found by the method given in our Theorem 2. This method is based on the explicit construction (Theorem 1) of the maps of the vertex set that induce largest matchings in any bipartite subgraph of the n-dimensional cube for any n.     

On low-dimensional faces that high-dimensional polytopes must have

We prove that every five-dimensional polytope has a two-dimensional face which is a triangle or a quadrilateral. We state and discuss the following conjecture: For every integerk1 there is an integer f(k) such that everyd-polytope,df(k), has ak-dimensional face which is either a simplex or combinatorially isomorphic to thek-dimensional cube.We give some related results concerning facet-forming polytopes and tilings. For example, sharpening a result of Schulte [25] we prove that there is no face to face tiling of ⁵ with crosspolytopes.Supported in part by a BSF Grant and by I.H.E.S, Bures-Sur-Yvette.     

Crumpled Cube and Solid Horned Sphere Space Fillers

We construct two classes of wildly embedded space fillers of R³. First, every crumpled cube is shown to have an embedding in R³ that admits a monohedral tiling of R³. Second, a solid Alexander horned sphere with a topologically trivial interior is shown to admit a monohedral tiling of a cube and hence R³. By joining a solid horned sphere with compact polyhedral 3-submanifolds of R³ with one boundary component, we construct space fillers homeomorphic to the polyhedral submanifolds but of different embedding types. Using the suitably embedded crumpled cubes instead of a solid horned sphere, space fillers of even more different topological types can be produced.