Boolean techniques for matroidal decomposition of independence systems and applications to graphs (Q1063611)

The sets of an independence system \(\Sigma\) on a finite set S can be characterized as the solutions of \(f(X)=0\) for a nondecreasing Boolean function f of \(| S|\) variables. Representing f as a product \(f_ 1f_ 2...f_ k\) corresponds to a kind of decomposition (union of independence systems) of \(\Sigma\) where those cases are most interesting for which each \(f_ i\) corresponds to a matroid on S: matroidal decomposition. Making extensive use of the algebraic techniques of Boolean calculations the paper studies these matroidal decompositions of independence systems. The functions f whose independence system is a matroid are characterized and it is shown that every nondecreasing f is the product of a finite number of such functions. Therefore, every independence system \(\Sigma\) has a matroidal decomposition and the minimal number of matroids in any of them is the matroidal number of \(\Sigma\). Finding matroidal decompositions via the associated Boolean functions is discussed. Specific results are then obtained for the case \(\Sigma =system\) of stable sets of a graph. For any positive integer k a class of graphs (complete k-partite graphs and k-polar graphs) with matroidal number k is constructed and the graphs with matroidal number 2 are characterized.