2011/03/15 by Patrick De Causmaecker, De Causmaecker, Patrick, Stefan De Wannemacker +1 · 1 citation
Computer Science · Mathematics · #05A18 06A07 06B05 #Advanced Algebra and Logic #Combinatorics (math.CO) #FOS: Mathematics #Number Theory (math.NT) #math.CO #math.NT #msc:05A18 #msc:06A07 #msc:06B05
paper · pdf · doi:10.48550/arxiv.1103.2877
15 pages
arxiv created 2011/03/15 · openalex publication_date 2011/03/15 · arxiv updated 2011/03/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This paper studies partitions in the space of antimonotonic boolean functions on sets of n elements. The antimonotonic functions are the antichains of the partially ordered set of subsets. We analyse and characterise a natural partial ordering on this set. We study the inter- vals according to this ordering. We show how intervals of antimonotonic functions, and a fortiori the whole space of antimonotonic functions can be partitioned as disjoint unions of certain classes of intervals. These in- tervals are uniquely determined by antimonotonic functions on smaller sets. This leads to recursive enumeration algorithms and new recursion relations. Using various decompositions, we derive new recursion formu- lae for the number of antimonotonic functions and hence for the number of monotonic functions (i.e. the Dedekind number).