MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $\{A_1,\ldots, A_m\}$ be a family of sets and $I=\{1, \ldots, m\}$. Assume for any $J\subset I$, $B_J=\bigcap_{i\in J}A_j$ satisfies $1\leq |B_J| \leq m-1$ as long as $|J|>1$.

We define a labelling of $J\subseteq I$ as follows. $l(J)=|B_J|$ if $|J|>1$ and $l(J)=m-1$ otherwise. Then we have the labelled poset $(2^I, \subseteq, l)$ (or labelled lattice).

Observe that $l\equiv m-1$ if $l(I)=m-1$. If $l(I)=m-2$, then there are two possibilities:

  1. $l(J)=m-2$ for all $J$ with $|J|=m-1$ or

  2. For a fixed $J_0$ with $|J_0|=m-1$, $l(J_0)=m-1$ and for all other $J$ with $|J|=m-1$, $l(J)=m-2$.

My question is this:

How can I order(partially is fine) this fixed lattice with respect to different labellings so that I will have the labels distributed "nicely"?

As you see I also am not sure of the type of the order. I like to see m-1's close to the top but also many of them. I also like to see large labels more than small labels...

any idea????


  1. If $J,K \subset I$ with $|J\cap K|>1$ and $l(J)=l(K)=m-1$, then $l(J\cup K)= m-1$.
  2. If $K\subset J$, then $l(K)\geq l(J)$.
  3. If $J_1, \ldots, J_s$ are maximal such that $l(J_i)=m-1$, then $|J_1|+\ldots+|J_s|=m$.
share|cite|improve this question
Does i different from j mean A_i is different from A_j? I note there are nonconstant labellings l which satisfy l(I) = m-1. I suspect there are more than two possibilities if I gets label m-2. Finally, it is not clear what nicely is. Do you want an order different from the lattice order which "does what" with respect to a labelling? Or do you want an order on the labellings themselves? More clarity is needed before I will think about this further. Gerhard "Ask Me About System Design" Paseman, 2011.05.10 – Gerhard Paseman May 10 '11 at 18:56
Sorry! I made a little mistake while defining $B_J$... It is fixed now. In the fixed version, if there is $B_J$ and $B_K$ with $|J|=|K|=m-1$ and $|B_K|=|B_J|=m-1$ then $|B_I|=m-1$. Sorry for the mistake.... – barish May 10 '11 at 19:51
Say I have two different sets $\{A_1,A_2,…,A_m\}$ and $\{C_1,C_2,…,C_m\}$ satisfying the same property. Let $l_A$ and $l_B$ be the labellings of $(2^I,\subseteq)$ induced by A's and C's. I want to be able to compare them. Hey! This tells me that I need an equivalence relation, not a partial order relation. But after the equivalence relation, I should be able to order the equivalence classes.... – barish May 10 '11 at 19:59
I am trying to order labellings of the same poset $(2^I,\subseteq)$ where $I=\{1,\ldots, r}$ and $l$ is a label induced by a family of sets $\{A_1, \ldots, A_{m-1}\}$ as in the original posting. – barish May 10 '11 at 20:03

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.