Decomposition of graphs and monotone formula size of homogeneous functions (Q1071036): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(2 intermediate revisions by 2 users not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4830805 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: An Algorithm for the Computation of Linear Forms / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4172915 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 10:48, 17 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Decomposition of graphs and monotone formula size of homogeneous functions |
scientific article |
Statements
Decomposition of graphs and monotone formula size of homogeneous functions (English)
0 references
1986
0 references
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.
0 references
graph partition
0 references
graph decomposition
0 references
complete bipartite graphs
0 references
monotone formula
0 references
quadratic function
0 references
uniform hypergraphs
0 references
homogeneous functions
0 references