3
$\begingroup$

I am given a (smallish, say $n=14$ element) set $X$, and a set $R$ of (a few hundred) quadruples of elements $(a, b, c, d)$ with $a,b,c, d\in X$.

I want to construct lattices on $X$, such that for all incomparable $a, b\in X$ the quadruple $(a,b,a\vee b, a\wedge b)$ is in $R$.

A trivial solution is to use an $n$-element chain as the lattice, which already gives me $14!=$a huge number of lattices. Thus, in a first step I'd like to find all non-isomorphic lattices. (Aside: is there a lattice structure on the set of isomorphism types of lattices on $n$ elements?)

Currently, I do not have a clue how many lattices I could build with my set, but I am certainly more interested in lattices with many incomparable elements.

As a first step, I determined which pairs $a,b$ do not occur as first two elements in one of the quadruples in $R$, because these must be comparable. In the first case I'm interested in, there are a dozen of these.

How could I do an exhaustive search?

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ Note that a and a join b are comparable. I suggest the next step is to look at those pairs formed from the first and third elements of each quadruple. In particular, if a and c are identical, b must be below a. Gerhard "See About The Pecking Order" Paseman, 2020.07.04. $\endgroup$
    – Gerhard Paseman
    Commented Jul 4, 2020 at 14:44
  • $\begingroup$ Sorry, I should have mentioned that the quadruples are really four-element-subsets, that is, a,b,c, and d are all distinct. $\endgroup$
    – Martin Rubey
    Commented Jul 4, 2020 at 15:49
  • $\begingroup$ Just so I am clear, can you explain the meaning of a meet c? Since you have only a and b as input, I want to understand the fourth coordinate of the output. Gerhard "For A Meeting Of Minds" Paseman, 2020.07.04. $\endgroup$
    – Gerhard Paseman
    Commented Jul 4, 2020 at 17:54
  • $\begingroup$ Sorry, that was a typo! $\endgroup$
    – Martin Rubey
    Commented Jul 4, 2020 at 18:25

1 Answer 1

Reset to default
2
$\begingroup$

You have an interesting kind of partitioning problem here. (Maybe that's why you are using lattices.)

One thing that should be noted. If d is a join b for some given a and b which are incomparable, then d is NOT a meet c for any c in the lattice. So when you focus on the first coordinate a, you immediately divide X minus a into three sets: those above a, those below a, and those that are incomparable to a..

This suggests an approach. Fix a, and look at the quadruples which have a in the first two coordinates. If two of the quadruples place d as being both above a and incomparable to a, then those two are incompatible conditions; one of them has to be thrown out, which means one of the b's that might lead to the conflict has to be comparable to b.

I recommend fixing a (or a small subset A which you assume to be an antivirus in the lattice), and see what inconsistencies you can generate. These inconsistencies will then inform you of comparability relations among the elements. Even if you have just one pair of incomparable elements, that will determine two other elements, and now you have less than 12! lattices to deal with. If nothing else, you can learn which three element subsets can be antichains in the lattice.

Gerhard "Let's Join Our Heads Together" Paseman, 2020.07.04.

Improve this answer
$\endgroup$
5
  • $\begingroup$ When you say "antivirus" here, do you mean "antichain"? Either this is a lattice term I don't know, or we all have the word "virus" entirely too much on our minds, or autocomplete strikes again... $\endgroup$
    – Nathan Reading
    Commented Jul 6, 2020 at 17:39
  • $\begingroup$ Oh no! I forgot my mask when posting that! Gerhard "Let's Blame This On Spellcheck" Paseman, 2020.07.06. $\endgroup$
    – Gerhard Paseman
    Commented Jul 6, 2020 at 17:50
  • $\begingroup$ I support not editing out the typo. It's such a timely typo. Nathan "Wish I Could Generate Cool Middle Names Like Gerhard" Reading, 2020.07.06. $\endgroup$
    – Nathan Reading
    Commented Jul 6, 2020 at 21:05
  • $\begingroup$ Practice makes tolerable. You are invited to copy the style, but not the content. Gerhard "Don't You Steal My Signatures!" Paseman, 2020.07.06. $\endgroup$
    – Gerhard Paseman
    Commented Jul 6, 2020 at 21:46
  • $\begingroup$ No, I would never dream of copying the style (outside of this little exchange). Nathan "There Can Only Be One Gerhard '...' Paseman" Reading $\endgroup$
    – Nathan Reading
    Commented Jul 6, 2020 at 23:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .