Thema der Dissertation:
Growth of Bilinear Maps Thema der Disputation:
Growth of polyominoes
Growth of Bilinear Maps Thema der Disputation:
Growth of polyominoes
Abstract: A polyomino is an edge-connected set of cells in the square lattice. Although the notion is simple and natural, many problems related to polyominoes are open, namely computing efficiently the number of polyominoes A(n) with n cells and estimating its exponential growth constant λ = lim{n→∞} A(n)^(1/n), which is known as Klarner's constant. The best algorithm for the former problem still suffers the exponential time complexity, whose base can be decreased usually by using more space. It follows that the natural way to bound λ from below by A(n)^(1/n) asks for a lot of computation. The best approach for a bound so far is by considering twisted cylinders, a model that is similar to polyominoes but a bit simpler to compute. This allows the lower bound to just exceed 4 by Barequet, Rote, and Shalah in 2016, which is close to the believed value λ ≈ 4.06. The known upper bounds are however not so good: the bound 4.65 has existed since 1973 by Klarner and Rivest, and only very recently got improved to 4.53 in 2022 by Barequet and Shalah, which actually asks for a good deal of computation. Related aspects and new approaches will be also discussed.
Zeit & Ort
18.12.2023 | 12:30
Seminarraum 053
(Fachbereich Mathematik und Informatik, Takustr.9, 14195 Berlin)