Geodesic
Monotone Formula Size of homogeneous Functions
Séminaire lotharingien de combinatoire, Tome 09 (1983)

Voir la notice de l'acte provenant de la source Séminaire Lotharingien de Combinatoire website

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 paper has been finally published under the same title in Acta Inform. 23 (1986), 689-696. 

@article{SLC_1983_09_a2,
     author = {Siegfried Bublitz},
     title = {Monotone {Formula} {Size} of homogeneous {Functions}},
     journal = {S\'eminaire lotharingien de combinatoire},
     publisher = {mathdoc},
     volume = {09},
     year = {1983},
     url = {http://geodesic.mathdoc.fr/item/SLC_1983_09_a2/}
}
TY  - JOUR
AU  - Siegfried Bublitz
TI  - Monotone Formula Size of homogeneous Functions
JO  - Séminaire lotharingien de combinatoire
PY  - 1983
VL  - 09
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SLC_1983_09_a2/
ID  - SLC_1983_09_a2
ER  - 
%0 Journal Article
%A Siegfried Bublitz
%T Monotone Formula Size of homogeneous Functions
%J Séminaire lotharingien de combinatoire
%D 1983
%V 09
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SLC_1983_09_a2/
%F SLC_1983_09_a2
Siegfried Bublitz. Monotone Formula Size of homogeneous Functions. Séminaire lotharingien de combinatoire, Tome 09 (1983). http://geodesic.mathdoc.fr/item/SLC_1983_09_a2/