Embedding dualities for set partitions and for relational structures

作者：Jelinek Vit^*; Klazar Martin

来源：European Journal of Combinatorics, 2011, 32(7): 1084-1096.

DOI：10.1016/j.ejc.2011.03.010

We show that for a set F of forbidden set partitions and an integer k there is a finite collection D of partitions of ordinals, such that any finite partition with at most k blocks avoids all the elements of F if and only if it is contained in at least one element of D. Using this result, we reprove rationality of the generating function enumerating a hereditary class of set partitions with a bounded number of blocks. We show that this result does not extend to partitions with an unbounded number of blocks.
We also consider hereditary classes of relational structures. We give a characterization of those classes that can be expressed as classes of finite substructures of a finite collection of (possibly infinite) relational structures.

• 出版日期2011-10