

Title: 
New Results on Tripod Packings 
Author(s): 
Östergård, Patric R.J.
;
Pöllänen, Antti

Date: 
20190315 
Language: 
en 
Pages: 
14 114 
Department: 
Department of Communications and Networking 
Series: 
Discrete and Computational Geometry 
ISSN: 
01795376 14320444 
DOInumber: 
10.1007/s0045401800122

Subject: 
Theoretical Computer Science, Geometry and Topology, Discrete Mathematics and Combinatorics, Computational Theory and Mathematics, 111 Mathematics

Keywords: 
Clique, Monotonic matrix, Packing, Semicross, Stein corner, Tripod, 52C17, Theoretical Computer Science, Geometry and Topology, Discrete Mathematics and Combinatorics, Computational Theory and Mathematics, 111 Mathematics

» Show full item record


Citation:
Östergård , P R J & Pöllänen , A 2018 , ' New Results on Tripod Packings ' Discrete and Computational Geometry , pp. 114 . DOI: 10.1007/s0045401800122

Abstract:
Consider an n× n× n cube Q consisting of n 3 unit cubes. A tripod of order n is obtained by taking the 3 n 2 unit cubes along three mutually adjacent edges of Q. The unit cube corresponding to the vertex of Q where the edges meet is called the center cube of the tripod. The function f(n) is defined as the largest number of integral translates of such a tripod that have disjoint interiors and whose center cubes coincide with unit cubes of Q. The value of f(n) has earlier been determined for n≤ 9. The function f(n) is here studied in the framework of the maximum clique problem, and the values f(10) = 32 and f(11) = 38 are obtained computationally. Moreover, by prescribing symmetries, constructive lower bounds on f(n) are obtained for n≤ 26. A conjecture that f(n) is always attained by a packing with a symmetry of order 3 that rotates Q around the axis through two opposite vertices is disproved.


Permanent link to this item:
http://urn.fi/URN:NBN:fi:aalto201808214591
