Geodesic
Enumeration of Certain Classes of Antichains
Publications de l'Institut Mathématique, _N_S_97 (2015) no. 111, p. 69

Voir la notice de l'article provenant de la source eLibrary of Mathematical Institute of the Serbian Academy of Sciences and Arts

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.
DOI : 10.2298/PIM140406001K
Classification : 05C30, 05C65
Keywords: exact enumeration, monotone Boolean function, hypergraph, antichain, cover, bipartite graph, digraph, coloring of a digraph 
@article{10_2298_PIM140406001K,
     author = {Goran Kilibarda},
     title = {Enumeration of {Certain} {Classes} of {Antichains}},
     journal = {Publications de l'Institut Math\'ematique},
     pages = {69 },
     publisher = {mathdoc},
     volume = {_N_S_97},
     number = {111},
     year = {2015},
     doi = {10.2298/PIM140406001K},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.2298/PIM140406001K/}
}
TY  - JOUR
AU  - Goran Kilibarda
TI  - Enumeration of Certain Classes of Antichains
JO  - Publications de l'Institut Mathématique
PY  - 2015
SP  - 69 
VL  - _N_S_97
IS  - 111
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.2298/PIM140406001K/
DO  - 10.2298/PIM140406001K
LA  - en
ID  - 10_2298_PIM140406001K
ER  - 
%0 Journal Article
%A Goran Kilibarda
%T Enumeration of Certain Classes of Antichains
%J Publications de l'Institut Mathématique
%D 2015
%P 69 
%V _N_S_97
%N 111
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.2298/PIM140406001K/
%R 10.2298/PIM140406001K
%G en
%F 10_2298_PIM140406001K
Goran Kilibarda. Enumeration of Certain Classes of Antichains. Publications de l'Institut Mathématique, _N_S_97 (2015) no. 111, p. 69 . doi: 10.2298/PIM140406001K

Cité par Sources :