"Representation Capacity" of Finite Lattice Ordered Modules

86 Views Asked by At

Apologies for what is probably a very basic question, but I am looking for references for what sort of lattices can be represented in what I think should be called something like "finite lattice-ordered modules."

The objects in question are tuples with dimension $d$, where the order between tuples is defined by pointwise $\ge$ as in a Riesz space or Banach lattice, but the elements are only allowed to take values from the integers $\{1,...,k\}$.

Ultimately I'd like to know what can be represented in the unit hypercube of a Riesz space with a requirement of some margin $m>0$ of separation in the order relation, but I assume reduction to this finite integer case is the best way to go about this.

I'm interested in questions of representation depending on the sizes of $d$ and $k$. For example, I can see that I can create a totally ordered set of depth $dk$ using the dictionary ordering. Further, if I add $e$ extra dimensions I can clearly union at least $2^e$ disjoint lattices using a binary code of $\top$ and $\bot$ (probably more depending on $k$).

The end goal is to be able to look at a given lattice and have some idea of what size of $d$ and $k$ one would need to represent it. I could write this as an integer linear programming feasibility problem, but those are NP-hard in general and I'm hoping some branch of lattice theory could say something nontrivial here.

Even better would be a construction of the lattice and an analysis of how the representation changes when adding new elements or "edges." I am clearly very naive on this subject but I imagine adding an arbitrary edge between two disjoint sublattices could change the representation quite a bit.

I can see a few basic facts about this sort of representation, but I assume that others have studied this before and I would be very interested if anyone could even point me in the direction of good books/notes/monographs exploring this subject, or even what the proper name of the subject is.

1

There are 1 best solutions below

0
On BEST ANSWER

The short answer is: the notion of dimension.

Tom Trotter wrote a book on the topic.

https://books.google.com/books/about/Combinatorics_and_partially_ordered_sets.html?id=oe-EAAAAIAAJ

https://books.google.com/books?id=HYnuHkBbWiUC&pg=PA33&lpg=PA33&dq=ORDAL+dimension&source=bl&ots=J0FFpCk2i-&sig=h7Isn-RS2HJq0ZG1zD5kEgTxUXc&hl=en&sa=X&ved=0ahUKEwjAwdytxujTAhUlxYMKHfaZBIYQ6AEIMTAB#v=onepage&q=ORDAL%20dimension&f=false

The ORDAL conference has had a couple papers on what you might be interested in.

From Birkhoff's Theorem, every finite distributive lattice is the lattice of down-sets (order ideals) of a finite poset P. You are interested in the case where P is a disjoint sum of d linearly ordered sets each of size k-1.

Pouzet (or maybe it was Erne) asked some relevant open questions about algebraic dimension versus order dimension in the volume "Ordered Sets" edited by Ivan Rival.