Describing join-irreducible Boolean functions via their hypergraphs
by
Miguel Couceiro
University of Luxembourg
Coauthors: Moncef Bouaziz, Maurice Pouzet

In this talk we are interested in the join-irreducible elements of the poset [(W)\tilde] associated with the simple minor quasi-ordering of Boolean functions. This quasi-order can be described as follows: given two Boolean functions g and f, g is said to be a simple minor of f if g can be obtained from f by identification of variables, permutation of variables and addition of inessential variables.

We will consider the problem of determining the join-irreducible members of [(W)\tilde], i.e., those elements having a unique lower cover in [(W)\tilde]. Rather than taking a direct approach by looking into [(W)\tilde], we attack this problem by looking at Boolean functions as hypergraphs. This achieved by making use of the natural correspondence between multilinear polynomials over the two-element field and hypergraphs. To work in complete analogy with the Boolean function setting, we will also mimic the simple minor relation in the realm of hypergraphs. As we will see, join-irreducibility translates into a combinatorial property of hypergraphs. As a noteworthy criterion, we have that those hypergraphs with 2-set transitive automorphism groups yield join-irreducible members of [(W)\tilde]. As particular cases, we completely characterize join-irreducibility among Steiner systems and explicitly describe those simple graphs yielding join-irreducible members of [(W)\tilde].

Date received: March 31, 2008