From logical gates synthesis to chromatic bicritical clutters

The synthesis of logical gates by means of basic gates leads very naturally to the concept of clones of boolean functions and the corresponding lattic e of clones largely studied by E. Post; a deep investigation into the clone s of "positive functions" leads to the problem of characterizing their mini mal functions; the canonical bijection between positive functions and Spern er hypergraphs (also called clutters) allows one to define (associated with these minimal functions) chromatic bicritical clutters which are nothing e lse than clutters H having the property that, for every edge e, the clutter whose edges are those of H disjoint from e, has a chromatic number two les s than that of H. The bicritical clutters which are graphs are the source o f a conjecture from Lovasz (1966) which is still open: complete graphs are the only bicritical graphs! This survey is an attempt to grasp the (combina torial and gate-theoretical) properties of these clutters, many of which in herit from some well-known properties of self-transversal clutters (which a re exactly the non-trivial bicritical clutters of chromatic number three). New results are given for these clutters (mainly in corresponding gates syn thesis). Even if older results have been proved and appeared in previous pa pers (from 1965 to 1983), we have choosen to recall all these proofs in ord er to make the paper self-contained. (C) 1999 Elsevier Science B.V. All rig hts reserved.