Séminaire Lotharingien de Combinatoire, B09c (1983).
[Formerly: Publ. I.R.M.A. Strasbourg, 1984, 230/S-09, p.
Monotone Formula Size of homogeneous Functions
We show that every graph on n nodes can be partitioned by a
number of complete bipartite graphs with
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
The paper has been finally published under the same title in
Acta Inform. 23 (1986), 689-696.