EMIS ELibM Electronic Journals Publications de l'Institut Mathématique, Nouvelle Série
Vol. 97(111), pp. 69–87 (2015)

Previous Article

Next Article

Contents of this Issue

Other Issues

ELibM Journals

ELibM Home


Pick a mirror



Goran Kilibarda

Department of Mathematics, ALFA University, Belgrade, Serbia

Abstract: An antichain is here regarded as a hypergraph that satisfies the following property: neither of every two different edges is a subset of the other one. The paper is devoted to the enumeration of antichains given on an n-set and having one or more of the following properties: being labeled or unlabeled; being ordered or unordered; being a cover (or a proper cover); and finally, being a $T_0$-, $T_1$- or $T_2$-hypergraph. The problem of enumeration of these classes comprises, in fact, different modifications of Dedekind's problem. Here a theorem is proved, with the help of which a greater part of these classes can be enumerated. The use of the formula from the theorem is illustrated by enumeration of labeled antichains, labeled $T_0$-antichains, ordered unlabeled antichains, and ordered unlabeled $T_0$-antichains. Also a list of classes that can be enumerated in a similar way is given. Finally, we perform some concrete counting, and give a table of digraphs that we used in the counting process.

Keywords: exact enumeration; monotone Boolean function; hypergraph; antichain; cover; bipartite graph; digraph; coloring of a digraph

Classification (MSC2000): 05C30; 05C65

Full text of the article: (for faster download, first choose a mirror)

Electronic fulltext finalized on: 16 Apr 2015. This page was last modified: 21 Apr 2015.

© 2015 Mathematical Institute of the Serbian Academy of Science and Arts
© 2015 FIZ Karlsruhe / Zentralblatt MATH for the EMIS Electronic Edition