21-25 August 2012
Portorož, Slovenia
UTC timezone
Home > Timetable > Contribution details
PDF | XML

BOOTSTRAP PERCOLATION AND CUBE DISMANTLING

Presented by Dr. Janos BARAT
Type: Oral presentation

Content

An $n\times n\times n$ cube is made from $n^3$ unit cubes. Two such cubes are neighbours if they touch along a face. In each step of a dismantling process, we may remove a small cube that has precisely three neighbours. A move is {\it balanced} if the three neighbours are in three orthogonal directions. In the extremal case, there are $n^2$ independent small cubes left at the end of the dismantling. We call this set of cubes a {\it solution}. If a solution is projected in three orthogonal directions and we get the entire $n\times n$ square in each direction, then the solution is {\it perfect}. We show that it is possible to use a greedy algorithm to test whether a set of cubes forms a solution. For every $n\ge 2$ we find at least $n$ perfect solutions, and we use our greedy algorithm to count the perfect solutions for $n\le6$. Perfect solutions turn out to be precisely those which can be reached using only balanced moves. Every perfect solution corresponds naturally to a Latin square. If our dismantling process is reversed we get a build-up process very closely related to well-studied models of bootstrap percolation. We show that in an important special case our build-up reaches the same maximal position as bootstrap percolation. There are several computational aspects in the above discoveries. We will highlight these segments in our presentation.

Place

Location: Portorož, Slovenia
Address: University of Primorska, Faculty of Tourism Studies, Obala 11a, SI-6320 Portorož - Portorose, Slovenia
Room: VP1

Primary authors

More

Co-authors

More