Springe direkt zu Inhalt

Growth of polyominoes and of bilinear maps

Dec 18, 2023 | 12:30 PM s.t. - 02:00 PM

The Ph.D. defense starts with a 25' lecture about

  • Growth of polyominoes

(see below for the abstract), which is followed by a discussion and
a short presentation of the Ph.D. thesis with the title:

  • Growth of bilinear maps

Abstract of the first talk: Growth of polyominoes

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.

Time & Location

Dec 18, 2023 | 12:30 PM s.t. - 02:00 PM

Seminarraum 053
Institut für Informatik
Takustraße 9
Freie Universität Berlin

Freie Universität Berlin
Technische Universität Berlin
Humboldt-Universität zu Berlin
Deutsche Forschungsgemeinschaft (DFG)