×

New results on tripod packings. (English) Zbl 1407.52019

Summary: Consider an \(n \times n \times n\) cube \(Q\) consisting of \(n^3\) unit cubes. A tripod of order \(n\) is obtained by taking the \(3n-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 \leq 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 \leq 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.

MSC:

52C17 Packing and covering in \(n\) dimensions (aspects of discrete geometry)
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Ahlswede, R., Aydinian, H., Khachatrian, L.H.: Unidirectional error control codes and related combinatorial problems. In: Proceedings of the 8th International Workshop on Algebraic and Combinatorial Coding Theory, Tsarskoe Selo, Russia, 8-14 September, 2002, pp. 6-9
[2] Golomb, S.W.: A general formulation of error metrics. IEEE Trans. Inf. Theory 15(3), 425-426 (1969) · Zbl 0172.43302
[3] Hamaker, W., Stein, S.: Combinatorial packing of \[{\mathbb{R}}^3\] R3 by certain error spheres. IEEE Trans. Inf. Theory 30(2), 364-368 (1984) · Zbl 0552.05025
[4] Kaski, P., Östergård, P.R.J.: Classification Algorithms for Codes and Designs. Algorithms and Computation in Mathematics, vol. 15. Springer, Berlin (2006) · Zbl 1089.05001
[5] Kløve, T., Luo, J., Yari, S.: Codes correcting single errors of limited magnitude. IEEE Trans. Inf. Theory 58(4), 2206-2219 (2012) · Zbl 1365.94521
[6] Niskanen, S., Östergård, P.R.J.: Cliquer User’s Guide: Version 1.0. Technical report T48. Communications Laboratory, Helsinki University of Technology, Espoo (2003)
[7] Östergård, P.R.J.: A fast algorithm for the maximum clique problem. Discrete Appl. Math. 120(1-3), 197-207 (2002) · Zbl 1019.05054
[8] Östergård, P.R.J., Pöllänen, A.: Dataset for New results on tripod packings [Dataset]. Zenodo (26 April 2018). https://doi.org/10.5281/zenodo.1230276
[9] Stein, S.K.: Factoring by subsets. Pac. J. Math. 22(3), 523-541 (1967) · Zbl 0149.26501
[10] Stein, S.: Packings of \[{\mathbb{R}}^nRn\] by certain error spheres. IEEE Trans. Inf. Theory 30(2), 356-363 (1984) · Zbl 0541.52007
[11] Stein, S.K., Szabó, S.: Algebra and Tiling: Homomorphisms in the Service of Geometry. Carus Mathematical Monographs, vol. 25. Mathematical Association of America, Washington, DC (1994) · Zbl 0930.52003
[12] Szabó, S.: Monotonic matrices and clique search in graphs. Ann. Univ. Sci. Bp. Sect. Comput. 41, 307-322 (2013) · Zbl 1289.94086
[13] Tiskin, A.: Packing tripods: narrowing the density gap. Discrete Math. 307(16), 1973-1981 (2007) · Zbl 1118.05013
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.