Decomposition of graphs and monotone formula size of homogeneous functions (Q1071036)

We show that every graph on n nodes can be partitioned by a number of complete bipartite graphs with \(O(n^ 2/\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. That means we disprove the single-level-conjecture for formulae.