A search for optimal order ideals

2011-08-11T18:47:41Z

At the behest of Gerhard Paseman I'll describe the problem that I alluded to in name for a partial order.

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|},$$

where $S \Delta T$ denotes the symmetric difference. If $ p \in (0,1)$ say that a finite subset $A \subset M$ is optimal at $p$ if $f_A(p) \ge f_B(p)$ for all subsets $B \subset M$ with $|B| = |A|$. Say that $A$ is optimal, 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)$.

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.

In (Gordon, Miller, Ostapenko) 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 one of his papers .

A search for optimal order ideals - MathOverflow

A search for optimal order ideals