Advanced Seminar on Polyominoes and Polycubes - 236804
Prof. Gill Barequet (barequet@cs.technion.ac.il)
Fall 2014-15


Syllabus

This seminar will cover most of the literature on polyominoes and polycubes enumeration and asymptotic growth rates.
See seminar announcement.


News and Messages

(18/Dec/14)
In the wake of Hanukkah, the meeting of Monday, December 22, 2014, is canceled.

(24/Oct/14)
I posted below your assigned dates and papers. Miraculously I was able to fulfill the date requests of all students.
The locations of the papers were announced via e-mail.
All lectures should be 50 minutes, even if the talk is on more than one paper, so please prepare accordingly.
Please send me the final presentations in any reasonable format (e.g., ppt or pdf) 3 days before the lecture (that is, till Friday preceding your talk), so that I can upload it to the web page for the benefit of the other students. If you later have a corrected/updated version (which does not deviate significantly from the original one), I will replace as needed.
If your lecture is about more than one paper, it is up to you to decide whether to create a separate presentation for each paper or to create one unified presentation - use your common sense.

(23/Oct/14)
I brought the issue of the language, in which student talks will be given, to the highest ranks in the faculty, namely the dean and three vice deans. The conclusion was that the talks will be given in Hebrew, but students may still give them in English if they wish to.

(23/Oct/14)
Today will be the last day for registering to the mailing list (details below) and for requesting specific dates for the talk.

(18/Oct/14)
This seminar is not related in contents to the course Computational Geometry (236719) which is also given this semester, but the course is highly recommended for those interested in geometric data structures, algorithms, and combinatorial structures. It (236719) is also prerequisite for the course Discrete Algorithmic Geometry (238719, the only active 238 course) which will be given next semester.

(13/Oct/14)
Students in the seminar are requested to send me asap their preferences about the dates of their talks. Requests will be handled in the order or receipt.

(7/Oct/14)
The meeting of Monday, November 24, is canceled.

(6/Oct/14)
Students in the seminar are requested to contact me asap in order to fix dates and paper(s) for their talks.

(20/Sep/14)
1. Students who register to the seminar are requested to join the mailing-list of the course. In order to do that, please send me by e-mail your name, id number, faculty, and degree. (This is in addition to the formal registration to the seminar!)
2. Attendance: Let n be the number of meetings with talks. Every student is expected to attend at least Min(10,n-2) meetings.


Bibliography

See here.


Seminar Plan

(1) Monday 20/Oct/14:
Gill Barequet: Introduction (presentation)

(2) Monday 27/Oct/14:
1. Ariel Haviv:
Isoperimetrical polyominoes (Clarke, 1980); and
The number of convex polyominoes with given perimeter (Kim, 1988, presentation of both papers)
2. (no talk)

(3) Monday 3/Nov/14:
1. Liran Kurtz:
Symmetry of cubical and general polyominoes (Lunnon, 1972); and
Counting multidimensional polyominoes (Lunnon, 1975, presentation of both papers)
2. (no talk)

(4) Monday 10/Nov/14:
1. Pavlo Kogan:
Cell growth problems (Klarner, 1967, presentation)
2. Alon Bezinian:
Counting polyominoes (Lunnon, 1971, presentation)

(5) Monday 17/Nov/14:
No meeting

(-) Monday 24/Nov/14:
Meeting canceled

(6) Monday 1/Dec/14:
1. Kujan Lauz:
Counting polyominoes: Yet another attack (Redelmeier, 1981, presentation)
2. Lina Musallam:
Counting d-dimensional polycubes and nonrectangular planar polyominoes (Aleksandrowicz and Barequet, 2009); and
Counting polycubes without the dimensionality curse (Aleksandrowicz and Barequet, 2009, presentation of both papers)

(7) Monday 8/Dec/14:
1. Nir Sagi:
A procedure for improving the upper bound for the number of n-ominoes (Klarner and Rivest, 1973, presentation)
2. Yael Nahari:
Algebraic langauges and polyominoes enumeration (Delest and Viennot, 1984, presentation)

(-) Monday 15/Dec/14:
No meeting (Hanukkah)

(8) Monday 22/Dec/14:
No meeting (Hanukkah)

(9) Monday 29/Dec/14:
1. Gal Lilos:
Animals, trees, and renewal sequences (Rands and Welsh, 1981/2, presentation)
2. Ori Brusilovsky:
Formulae and growth rates of high-dimensional polycubes (Barequet, Barequet, and Rote, 2010, presentation)

(10) Monday 5/Jan/15:
Gill B:
Counting polyominoes: A parallel implementation for cluster computing (Jensen, 2003); and
On the complexity of Jensen's algorithm for counting fixed polyominoes (Barequet and Moffie, 2007, presentation of both papers)

(11) Monday 12/Jan/15:
Mira Shalah:
Counting polyominoes on twisted cylinders (Barequet, Moffie, Ribó, and Rote, 2006); and
λ > 4 (Barequet, Rote, and Shalah, unpulished)

(12) Monday 19/Jan/15:
1. Tanya Tokar:
Counting lattice animals in high dimensions (Luther and Mertens, 2011, presentation)
2. (no talk)