Decomposition of graphs and monotone formula size of homogeneous functions
type: Item
instance of: scholarly article
title: Decomposition of graphs and monotone formula size of homogeneous functions
zbMATH Open document ID: 0585.05031
DOI: 10.1007/BF00264314
author: Siegfried Bublitz
published in: Acta Informatica
publication date: 1986-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C99
Mathematics Subject Classification ID: 05C65
zbMATH DE Number: 3937216
zbMATH Keywords: graph partition
zbMATH Keywords: graph decomposition
zbMATH Keywords: complete bipartite graphs
zbMATH Keywords: monotone formula
zbMATH Keywords: quadratic function
zbMATH Keywords: uniform hypergraphs
zbMATH Keywords: homogeneous functions
MaRDI profile type: Publication
cites work: Q4830805
cites work: An Algorithm for the Computation of Linear Forms
cites work: Q4172915
description: scientific article; zbMATH DE number 3937216