On a composition of independence systems by circuit identification (Q1186136): Difference between revisions

Let \(E\) be a finite set. A subset of the power set \({\mathcal I}\subset 2^ E\), is called an independence system if \(I\in{\mathcal I}\) and \(J\leq I\) implies \(J\in{\mathcal I}\). The independent set problem is ``given an independence system \({\mathcal I}\) for \(E\) and a real valued weight function \(w\) on \(E\), find an independent set \(I\in{\mathcal I}\) with maximum weight \((w(I)=\sum_{e\in I}w(e))\).'' In order to employ linear programming tools in solving this problem, one would like to be able to describe the polytope \(P({\mathcal I})\) (defined to be the convex hull in \(\mathbb{R}^ E\) of the collection of incidence vectors of the sets in \({\mathcal I})\) in terms of linear inequalities. The authors develop a composition for a class of independence structures which enables them to describe the polytope of the composition of two independence structures in terms of the polytopes of the original structures. This then leads to a solution of the independence problem of the structures in this class. Some specific examples from graph theory are worked out.