1
$\begingroup$

To be up front, I was helping my friend with his programming assignment and I stumbled upon the following sentence

List all the lattices (subsets of S) on S with size K

it later says that the partial order is defined as "is multiple of"

I don't quite understand what this means. Can someone explain the theory behind this?

I checked on wikipedia but there is a lot of jargon that I don't understand. Any assistance with this would be appreciated.

I should note that my mathematics is not the strongest.

$\endgroup$
1
  • 2
    $\begingroup$ What does your friend's textbook or class notes have to say about lattices? If it were me and I didn't know the term, and if I also thought I could still be of assistance, I would ask to look at these. However, I suspect I would probably just say "sorry, I don't know anything about lattices, so I don't think I can be of any help". That said, maybe some of the results from a google search for "lattice" {AND} "discrete mathematics" could help. $\endgroup$ Commented Oct 20, 2014 at 21:33

1 Answer 1

2
$\begingroup$

Consider a set A(say) containing N elements out of which you select all the subsets of size k. Now all you need to do is check whether the subset of size k is lattice or not.

By Definition, A Graph is considered to be Lattice if every pair of elements of the graph have a Greatest Lower Bound(GLB) and Least Upper Bound(LUB) existing.

Unfortunately checking this is quite tedious for large sets(although in your question it is given as n<20), best way according to me is counter example of a pair(which violates the above mentioned condition).

If two elements of the pair are interconnected then one of them is GLB and the other LUB, so they always satisfy the condition. Also if a pair doesn't have a GLB/LUB then they must be incomparable although converse doesn't hold.

P.S- I am doing the same sort of question, reach out in case you want to finish it off together even I haven't finished mine. Do let me know if you can come with better Algorithm for the same.

$\endgroup$

You must log in to answer this question.

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