1
$\begingroup$

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 $$ 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.

  • 1
    If I understand you correctly, your first partial order is simply the product partial order on $X^k$.2012-12-03
  • 0
    @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 :)2012-12-03
  • 0
    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!)2012-12-03
  • 0
    @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!2012-12-03
  • 0
    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.2012-12-03

0 Answers 0