Séminaire Lotharingien de Combinatoire, B09c (1983), 1 p.
[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.
Siegfried.Bublitz@c-lab.de
The following version is available:
The paper has been finally published under the same title in
Acta Inform. 23 (1986), 689-696.