Cube tiling and covering a complete graph

DOI10.1016/0012-365X(90)90388-XMaRDI QIDQ1173697zbMATH OpenOpenAlexFDO

Authors K. Corrádi, Sándor Szabó

Publication date 25 June 1992

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365x(90)90388-x

zbMATH Keywords

bipartite graphscomplete graphcovering

Mathematics Subject Classification ID

Combinatorial aspects of packing and covering (05B40) Combinatorial aspects of tessellation and tiling problems (05B45) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Review text

A conjecture on filling \(n\)-space with \(n\)-cubes due to Keller has been reformulated as a conjecture on graphs that states: if \(G_ 1,\dots,G_ n\) are bipartite graphs on \(2^ n\) vertices whose union is the complete graph on \(2^ n\) vertices, then each \(G_ i\) contains an edge \(e_ i\) for which \(G_ j\cup e_ i\) contains an odd cycle for each \(1\leq i\), \(j\leq n\), \(i\neq j\). Here the authors prove a special case in which each \(G_ i\) is the disjoint union of at most two regular complete bipartite subgraphs.

Recommendations

• A combinatorial approach for Keller's conjecture
• Keller’s cube-tiling conjecture is false in high dimensions
• A cube tiling of dimension eight with no facesharing

Cites work

• A reduction of Keller's conjecture
• Algebraic Tiling
• How Does a Complete Graph Split into Bipartite Graphs and How are Neighborly Cubes Arranged?
• scientific article; zbMATH DE number 3759062 (Why is no real title available?)
• scientific article; zbMATH DE number 3078637 (Why is no real title available?)
• Multiple tilings of \(n\)-dimensional space by unit cubes

Cited in

(9)

• Covering and tiling hypergraphs with tight cycles
• Rigid polyboxes and Keller's conjecture
• Towards resolving Keller's cube tiling conjecture in dimension seven
• Partitions and balanced matchings of an n-dimensional cube
• Rigidity and the chessboard theorem for cube packings
• On Keller's conjecture in dimension seven
• Komlós's tiling theorem via graphon covers
• The structure of cube tilings under symmetry conditions
• On the sphericity and cubicity of graphs

This page was built for publication: Cube tiling and covering a complete graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1173697)