A search for optimal order ideals - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T03:54:19Z http://mathoverflow.net/feeds/question/72709 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/72709/a-search-for-optimal-order-ideals A search for optimal order ideals Victor Miller 2011-08-11T18:47:41Z 2011-08-11T19:22:56Z <p>At the behest of Gerhard Paseman I'll describe the problem that I alluded to in <a href="http://mathoverflow.net/questions/72260/the-name-for-a-partial-order" rel="nofollow"><em>name for a partial order</em></a>.</p> <p>Let $M = M(\infty)$ denote the set of all finite subsets of the positive integers $\mathbb{N}$. As I mentioned in my other question, $M$ has a partial order defined as follows: If $S \in M$ and $i \ge 1$ is an integer, denote by $S_i$ the $i$-th largest element of $S$. We say that $S \ge_R T$ if $|S| \ge |T|$ and $S_i \ge T_i$ for $i = 1, \dots, |T|$. For any finite subset $A \subset M$ define the polynomial $$f_A(t) := \sum_{S \in A} \sum_{T \in A} t^{|S \Delta T|},$$</p> <p>where $S \Delta T$ denotes the symmetric difference. If $p \in (0,1)$ say that a finite subset $A \subset M$ is <em>optimal at $p$</em> if $f_A(p) \ge f_B(p)$ for all subsets $B \subset M$ with $|B| = |A|$. Say that $A$ is <em>optimal</em>, if there is some $p \in (0,1)$ for which $A$ is optimal at $p$. Say that $A$ is isomorphic to $B$ if there is a permutation $\pi \in S_{\infty}$ (permutations of $\mathbb{N}$ which only move a finite set of elements) and a subset $T \in M$ such that $B = \{ \pi(S) \Delta T : S \in A \}$. It's easy to see that if $A$ is isomorphic to $B$ then $f_A(t) = f_B(t)$.</p> <p>Another way of thinking of $M$ is to consider it to be infinite sequences of 0's and 1's with only a finite number of 1's (i.e. infinite bit-strings). Then cardinality becomes Hamming weight and symmetric difference becomes exclusive or. Isomorphic sets of bit-strings would be obtained from one another by permuting coordinates (every bit string in the set gets permuted in the same way), and then xoring everything with a common bit-string.</p> <p>In <a href="http://arxiv.org/pdf/0806.3284v2" rel="nofollow"> (Gordon, Miller, Ostapenko) </a> we proved that if $A$ is optimal then it is isomorphic to an order ideal for the order $\le_R$. For a fixed value $N$ for $|A|$ we were then able to make a search for all order ideals of size $N$, and then determine the optimal ones (for some $p$) among those. We were able to do this by looking at the subposet of $M$ of elements $S \in M$ such that $|\{ T : T \le_R S \}| \le N$. In particular we were interested in optimal sets whose cardinality is a power of 2. The search for cardinality 64 took about 1/2 hour. Unless we have a new idea the search for $N=128$ is out of the question. For $N=64$ there are 4384627 order ideals of cardinality 64, but less than 100 of them are optimal. Thus I was hoping that if there are theorems around about the structure of the order ideals of $M(\infty)$ that that might help us to make a more efficient search. In the previous question, Richard Stanley pointed out that the partial order that I was using had been studied before in <a href="http://math.mit.edu/~rstan/pubs/pubfiles/84.pdf" rel="nofollow"> one of his papers </a>.</p>