2012/09/20 by Stephen, Tamon, Yusun, Timothy
#05A05 #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Primary: 68W05 #Secondary: 06E30
paper · doi:10.48550/arxiv.1209.4623
Monotone Boolean functions (MBFs) are Boolean functions f: 0,1n → 0,1 satisfying the monotonicity condition x ≤ y ⇒ f(x) ≤ f(y) for any x,y ∈ 0,1n. The number of MBFs in n variables is known as the nth Dedekind number. It is a longstanding computational challenge to determine these numbers exactly - these values are only known for n at most 8. Two monotone Boolean functions are inequivalent if one can be obtained from the other by renaming the variables. The number of inequivalent MBFs in n variables was known only for up to n = 6. In this paper we propose a strategy to count inequivalent MBF's by breaking the calculation into parts based on the profiles of these functions. As a result we are able to compute the number of inequivalent MBFs in 7 variables. The number obtained is 490013148.