Algorithmic combinatorics based on slicing posets

AbstractA combinatorial problem usually requires enumerating, counting or ascertaining existence of structures that satisfy a given property B in a set of structures L. This paper describes a technique based on a generalization of Birkhoff's theorem of representation of finite distributive lattices that can be used for solving such problems mechanically and efficiently. Specifically, we give an efficient (polynomial time) algorithm to enumerate, count or detect structures that satisfy B when the total set of structures is large but the set of structures satisfying B is small. We illustrate our techniques by analyzing problems in integer partitions, set families, and set of permutations