Advanced Seminar on Polyominoes and Polycubes - 236801
Prof. Gill Barequet (barequet@cs.technion.ac.il)
Spring 2011-12


Syllabus

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


News and Messages

(15/May/12)
The talk of Yaakov W. was moved to Monday, June 18, 2012.

(14/May/12)
The meeting of Monday, June 18, 2012 will probably take place - see updated schedule below.

(10/May/12)
Amir B. wrote up a draft about the theoretical basis of analyzing symmetries of polycubes - see here.

(25/Feb/12)
A tentative program of the seminar (subject to minor changes) was published. The allocations of dates satisfy all your preferences. Please verify that all data are correct and mark the day of your lecture. The program covers all the interesting papers in the Math-CS research track (the statistical-physics literature is harder to comprehend and in most cases is semi-rigorous). I hope that you will enjoy the seminar.

(14/Feb/12)
Paper-allocation meetings will take place in my office (T-428) in Monday 20/2 10-14 and Tuesday 21/2 10-12 + 13-15. (More meetings will be set for those who cannot make it during these times.)

(08/Jan/12)
Manual registration to the seminar will take place tomorrow, January 9, 2012, in my office (T-428) at 14:30-16:30. Students who cannot make it at that time, but still want to register, are requested to email me.

(01/Jan/12)
1. Registration to the seminar is manual. See instructions here. If you are interested, please email me in advance.
2. 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!)
3. Attendance: Let n be the number of meetings with talks. Every student is expected to attend Min(10,n-2) meetings.


Bibliography

See here.


Seminar Plan

(1) Monday 12/Mar/12:
Gill Barequet: Introduction (presentation)

(2) Monday 19/Mar/12:
1. Artium Nihamkin:
Isoperimetrical polyominoes (Clarke, 1980); and
The number of convex polyominoes with given perimeter (Kim, 1988, presentation of both papers)

(-) Monday 26/Mar/12:
No meeting

(3) Monday 02/Apr/12:
1. Eran Arbel:
Symmetry of cubical and general polyominoes (Lunnon, 1972); and
Counting multidimensional polyominoes (Lunnon, 1975, presentation of both papers)
2. Maor Grinberg:
Algebraic langauges and polyominoes enumeration (Delest and Viennot, 1984, presentation)

(-) Monday 09/Apr/12:
No meeting (Passover break)

(4) Monday 16/Apr/12:
1. Avri Dahan:
Counting polyominoes (Lunnon, 1971, presentation)
2. Amir Belgi:
Counting hexagonal and triangular polyominoes (Lunnon, 1972, presentation, notes)

(-) Monday 23/Apr/12:
No meeting (Thursday-like studies)

(5) Monday 30/Apr/12:
1. Alex Ilgayev:
Cell growth problems (Klarner, 1967, presentation)
2. Hagar Dror:
A procedure for improving the upper bound for the number of n-ominoes (Klarner and Rivest, 1973, presentation)

(6) Monday 07/May/12:
1. Belal Kabat:
Animals, trees, and renewal sequences (Rands and Welsh, 1981/2, presentation)
2. Ido Senesh:
Generating functions for column-convex polyominoes (Delest, 1988, presentation)

(7) Monday 14/May/12:
1. Yulia Sher:
Counting polyominoes: Yet another attack (Redelmeier, 1981, presentation)
2. Olga Bramnik:
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)

(8) Monday 21/May/12:
1. Pini Solomovitz:
Counting lattice animals in high dimensions (Luther and Mertens, 2011, presentation)
2. (no talk)

(9) Monday 28/May/12:
1. David Keter:
Enumerations of lattice animals and trees (Jensen, 2001); and
Counting polyominoes: A parallel implementation for cluster computing (Jensen, 2003, presentation)
2. Shmuel Keter:
On the complexity of Jensen's algorithm for counting fixed polyominoes (Barequet and Moffie, 2007, presentation)

(10) Monday 04/Jun/12:
1. Roi Poranne:
Counting polyominoes on twisted cylinders (Barequet, Moffie, Ribó, and Rote, 2006, presentation)
2. Mira Shalah:
Formulae for polyominoes on twisted cylinders (Aleksandrowicz, Asinowski, Barequet, and Barequet, unpublished, presentation)

(11) Monday 11/Jun/12:
1. Nurit Schwabsky:
Formulae and growth rates of high-dimensional polycubes (Barequet, Barequet, and Rote, 2010, presentation)
2. Avi Stiefel:
A closed formula for the number of convex permutominoes (Disanto, Frosini, Pinzani, and Rinaldi, 2007, presentation)

(12) Monday 18/Jun/12:
1. Raeda Naamnieh:
A polyominoes-permutations injection and tree-like convex polyominoes (Aleksandrowicz, Asinowski, and Barequet, 2012, presentation)
2. Yaakov Weiss:
Asymptotic bounds for the number of convex n-ominoes (Klarner amd Rivest, 1974); and
On the number of convex polyominoes (Gessel, 2000, presentation of both papers)

(13) Monday 25/Jun/12:
1. Anastasia Shchukin:
Reverse search for enumeration (Avis and Fukuda, 1996, presentation)
2. Sarit Buzaglo:
Proper n-cell polycubes in n-3 dimensions (Asinowski, Barequet, Barequet, and Rote, unpublished, presentation)