2010/06/09 by Jiřı́ Matoušek, Jiří Matoušek, Matoušek, Jiří +2
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Computational Geometry and Mesh Generation #graph theory and CDMA systems #math.CO #msc:52B45
paper · pdf · doi:10.48550/arxiv.1006.1807
11 pages, 3 figures
arxiv created 2010/06/09 · arxiv updated 2010/06/10
A d-dimensional simplex S is called a k-reptile if it can be tiled without overlaps by simplices S1,S2,...,Sk that are all congruent and similar to S. For d=2, k-reptile simplices (triangles) exist for many values of k and they have been completely characterized by Snover, Waiveris, and Williams. On the other hand, for d > 2, only one construction of k-reptile simplices is known, the Hill simplices, and it provides only k of the form md, m=2,3,.... We prove that for d=3, k-reptile simplices (tetrahedra) exist only for k=m3. This partially confirms a conjecture of Hertel, asserting that the only k-reptile tetrahedra are the Hill tetrahedra. Our research has been motivated by the problem of probabilistic packet marking in theoretical computer science, introduced by Adler in 2002.