On Fri, Nov 29, 2002 at 06:38:41PM -0500, JP Grossman wrote:
First, if X and Y are in the orbit then the 1's of X are not a subset of the 1's of Y. For suppose this is the case. Write down the period starting with X:
X, ..., Y, ........, (X)
This is answering a different question; Allan Weschler's original post didn't ask for the states to be periodic---just, what is the maximum time before the state repeats some prior state. E.g. you can have X, ..., Y, ..., Y with no X's occuring between the two Y's. The case you're analyzing is the antichain case I referred to in my post: an antichain in a partially ordered set is a collection of elements such that no element is < than any other element. I think quite a bit of work has been done on studying maximal antichains in various contexts, although I'm not very familiar with it. My guess is that the set of all [n/2]-element subsets of n things is a maximum-size antichain, and I figure it's probably known whether or not this is true. This does better than the recursive inequality f(n+2) > 2 f(n) + 1 I talked about, for n big enough, and by combining with the comments I made you can do better than the size of an antichain. Interesting problem! Bill Thurston