0
$\begingroup$

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 .

$\endgroup$
3
  • $\begingroup$ Thank you for showing this problem. I assume in the definition of A isomorphic to B you want B= instead of A=. Also, I apologize for an earlier error. The partial order I and Libor Polak used involved multisets, not sets, of the positive integers. I shall contemplate upon this problem. Gerhard "Ask Me About System Design" Paseman, 2011.08.11 $\endgroup$ Aug 11, 2011 at 19:03
  • $\begingroup$ Also, it is easy for me to get confused. A in M suggests that A is a set of numbers. A finite set A from M is a finite subset of M. By a finite set A in M I am guessing you mean the latter, but I would expect A subset M instead of what you have, which is A in M. Can I consider it a typo, and mentally substitue the subset symbol for the member of symbol in those places to get your meaning? Gerhard "Ask Me About System Design" Paseman, 2011.08.11 $\endgroup$ Aug 11, 2011 at 19:11
  • $\begingroup$ @Gerhard: I fixed the typos (I think that I got all of them). One other thing: you can also define a different partial order on subsets of M: Say that $A \ge_D B$ if $f_A(t) \ge f_B(t)$ for all $t \in (0,1)$ (the $D$ is for dominates). It's necessary (but not sufficient) for $A$ to be maximal in this partial order (at least restricted to sets of cardinality $|A|$) in order for it to be optimal. I found empirically that almost all of the maximal sets for $N=64$ were optimal. $\endgroup$ Aug 11, 2011 at 22:36

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.