tailieunhanh - Báo cáo toán học: " THE THREE DIMENSIONAL POLYOMINOES OF MINIMAL AREA"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: THE THREE DIMENSIONAL POLYOMINOES OF MINIMAL AREA. | THE THREE DIMENSIONAL POLYOMINOES OF MINIMAL AREA Laurent ALONSO CRIN-INRIA Loria BP239 54506 Vandreuvre-les-Nancy France Raphael CERF CNRS Université Paris Sud Mathématique Batiment 425 91405 Orsay Cedex France Submitted December 21 1995 Accepted September 9 1996 Abstract. The set of the three dimensional polyominoes of minimal area and of volume n contains a polyomino which is the union of a quasicube j X j ỗ X j ớ ỗ 0 2 0 1 a quasisquare l X l e e 2 0 1 and a bar k. This shape is naturally associated to the unique decomposition of n j j ỗ j ớ l l e k as the sum of a maximal quasicube a maximal quasisquare and a bar. For n a quasicube plus a quasisquare or a quasicube minus one the minimal polyominoes are reduced to these shapes. The minimal area is explicitly computed and yields a discrete isoperimetric inequality. These variational problems are the key for finding the path of escape from the metastable state for the three dimensional Ising model at very low temperatures. The results and proofs are illustrated by a lot of pictures. 1991 Mathematics Subject Classification. 05B50 51M25 82C44. Key words and phrases. polyominoes minimal area isoperimetry Ising model. We thank an anonymous Referee for a very thorough reading and for many useful suggestions. L. Alonso is a Tetris expert. Typeset by AmS-TeX 1 THE ELECTRONIC JOURNAL OF COMBINATORICS 3 1996 R27 2 1. Introduction Suppose we are given n unit cubes. What is the best way to set them out in order to obtain a shape having the smallest possible area A little thinking suggests the following answer hrst build the greatest cube you can say j X j X j. Then complete one of its side or even two if you can to obtain a quasicube j X j S X j d where s 3 2 0 1 . With the remaining cubes build the greatest quasisquare possible l X l e e 2 0 1 and put it on a side of the quasicube. With the last cubes make a bar of length k l e and stick it against the quasisquare. Our .