Question

I think this SE site is the best fit for this question, if not please direct me somewhere else :).

For my Bsc. Thesis I've researched algorithms to determine the number of upper sets in a partially ordered set. Before I started, me and my professor searched for any prior research, unfortunately we couldn't find much except for research regarding the Dedekind number which is partially related.

While I'm finishing up my thesis my professor has expressed the wish to look for related work again to at least have some references and a half-decent 'prior/related work' chapter. So I'm looking for anything that is slightly related. However I keep running head first into pay-walls every time I find something that might be slightly related and I have a difficult time to asses the value of a paper based on it's front cover or the abstract. Of course my University has some contracts with some of these pay-walls but only mere luck directs me to one of these sometimes.

I'm looking for tips on where to find any related material concerning upper sets and upwards closure and if someone has experience and tips on writing a thesis in a field where there is not much prior work to cite from.

Answer 1

J.S. Provan and M.O. Ball, The complexity of counting cuts and of computing the probability that a graph is connected, SIAM J. Comput. 12 (1983) 777-78, show that the problem of computing the number of upper sets (often called dual order ideals or filters) is #P-complete. For some special posets the number of upper sets (or equivalently, lower sets aka order ideals) can be computed explicitly. Some examples appear in Enumerative Combinatorics, vol.1, 2nd ed., especially in the exercises to Chapter 3. See http://math.mit.edu/~rstan/ec/ec1. Some of the relevant exercises are 3.62, 3.66, 3.68, 3.74, 3.149, 3.170, 3.172. These last two are the deepest and most interesting.