Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. 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

Consider a finite set $X = \{x_1,\ldots,x_n\}$ whose elements are totally ordered. In fact, for concreteness, assume that $X$ is a set of reals, and without loss of generality assume that $x_i$ is the $i$th element in the sorted list of elements, i.e. $x_1 \leq x_2 \leq \ldots \leq x_n$. Let $<i_1,\ldots,i_k>$ denote the k-combination $\{x_{i_1},\ldots,x_{i_k}\}$from $X$, and for combinations $I,J\in {X\choose k}$, define $I \preceq J$ iff $i_m \leq j_m, \forall 1\leq m \leq k$.

My question is: what is the lattice generated by this partial order, and how can we characterize it? Is it well known, or isomorphic to something more familiar? Please forgive the vagueness of the question: I am primarily interested in learning what (if anything) this thing is called in combinatorics, and where I could learn more about it.

Thanks in advance!

PS: I am ultimately even more interested in another lattice defined by $I \subseteq J$ iff $\displaystyle\sum_{i\in I}x_i \leq \displaystyle\sum_{j\in J}x_j$, which clearly contains the first as a sub-lattice. I asked about the former since it seems simpler in some sense, but any remarks about either are quite welcome.

share|cite|improve this question
If I understand you correctly, your first partial order is simply the product partial order on $X^k$. – Brian M. Scott Dec 3 '12 at 2:32
@BrianM.Scott, thanks for the reply. Doesn't the product partial order on $X^k$ contain elements like $(1,1,1\ldots)$ which do not correspond to combinations, though? PS: congrats on your recent level-up :) – wvoq Dec 3 '12 at 3:17
Yes, it does; I wasn’t entirely sure whether you were allowing repetitions or not. If you’re not, then of course you get the restriction of the product partial order to the set of points not lying on any of the diagonal planes. (Thanks!) – Brian M. Scott Dec 3 '12 at 3:20
@BrianM.Scott, well if you want every combination to have a unique representation it would be the restriction to the set of points lying below the diagonal planes (i.e. we must have $i_1 < i_2 < \ldots i_k$). Anyway, can I infer from your answer that it is safe to say that the second lattice is, at least, not a totally bog-standard object in combinatorics that anyone would recognize? I ask because I'm in the sciences and always worry about naively re-deriving basic results that are already well-known to mathematicians. Thanks again! – wvoq Dec 3 '12 at 3:37
It might be more familiar to those who work more with such things $-$ my knowledge in that area is fairly superficial $-$ but I think it pretty safe to say that it’s not totally bog-standard to mathematicians in general. – Brian M. Scott Dec 3 '12 at 9: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.