Séminaire Lotharingien de Combinatoire, B09c (1983).
[Formerly: Publ. I.R.M.A. Strasbourg, 1984, 230/S-09, p. 112.]

Siegfried Bublitz

Monotone Formula Size of homogeneous Functions

Abstract. We show that every graph on n nodes can be partitioned by a number of complete bipartite graphs with O(n2/log n) nodes with no edge belonging to two of them. Since each partition corresponds directly to a monotone formula for the associated quadratic function, we obtain an upper bound for the monotone formula size of quadratic functions. Our method extends to uniform hypergraphs with fixed range and thus to homogeneous functions with fixed length of prime implicants. Finally, we give an example of a quadratic function where each monotone formula built from arbitrary partitions of the graph (double edges allowed) is not optimal. This means that we have disproved the single-level-conjecture for formulae.


The paper has been finally published under the same title in Acta Inform. 23 (1986), 689-696.