Any 2-asummable bipartite function is weighted threshold

作者：Herranz Javier^*

来源：Discrete Applied Mathematics, 2011, 159(11): 1079-1084.

DOI：10.1016/j.dam.2011.01.023

• Weighted threshold boolean functions
• Bipartite functions
• 2-asummability

Possible characterizations of which positive boolean functions are weighted threshold were studied in the 60s and 70s. It is known that a boolean function is weighted threshold if and only if it is k-asummable for every value of k. Furthermore, for some particular subfamilies of functions (those with up to eight variables, and graph functions), it is known that a function is weighted threshold if and only if it is 2-asummable.
In this work we prove that bipartite functions also satisfy this property: a bipartite function is weighted threshold if and only if it is 2-asummable. In a bipartite function the set of variables can be partitioned in two classes, such that all the variables in the same class play exactly the same role in the function.

• 出版日期2011-7-6