The still-Life density problem and its generalizations
| dc.creator | Elkies, Noam D. | |
| dc.date | 1999-05-31 | |
| dc.date.accessioned | 2026-07-07T05:29:18Z | |
| dc.date.available | 2026-07-07T05:29:18Z | |
| dc.description | A "still Life" is a subset S of the square lattice Z^2 fixed under the transition rule of Conway's Game of Life, i.e. a subset satisfying the following three conditions: 1. No element of Z^2-S has exactly three neighbors in S; 2. Every element of S has at least two neighbors in S; 3. Every element of S has at most three neighbors in S. Here a ``neighbor'' of any x \in Z^2 is one of the eight lattice points closest to x other than x itself. The "still-Life conjecture" is the assertion that a still Life cannot have density greater than 1/2 (a bound easily attained, for instance by {(x,y): x is even}). We prove this conjecture, showing that in fact condition 3 alone ensures that S has density at most 1/2. We then consider variations of the problem such as changing the number of allowed neighbors or the definition of neighborhoods; using a variety of methods we find some partial results and many new open problems and conjectures. | |
| dc.description | 29 pages, including many figures drawn as LaTeX "pictures" | |
| dc.identifier | https://arxiv.org/abs/math/9905194 | |
| dc.identifier | http://arxiv.org/abs/math/9905194 | |
| dc.identifier | Pages 228--253 of_Voronoi's Impact on Modern Science, Book I_ (P. Engel, H. Syta, eds.; Institute of Math., Kyiv 1998 = Vol.21 of Proc. Inst. Math. Nat. Acad. Sci. Ukraine) | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/78584 | |
| dc.subject | Combinatorics | |
| dc.subject | 05B40, 05B45 | |
| dc.title | The still-Life density problem and its generalizations | |
| dc.type | text |