A note on the non-spanning circuits of a matroid (Q1176034)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A note on the non-spanning circuits of a matroid |
scientific article |
Statements
A note on the non-spanning circuits of a matroid (English)
0 references
25 June 1992
0 references
The authors determine when a collection of subsets of a set \(E\) is the set of non-spanning circuits of a matroid on \(E\). Theorem 3. Let \({\mathcal C}'\) be a collection of subsets of a set \(E\) and \(k\) be a nonnegative integer. Then \({\mathcal C}'\) is the set of non-spanning circuits of a rank \(k\) matroid on \(E\) iff \({\mathcal C}'\) has the following properties: (i) No member of \({\mathcal C}'\) properly contains another. (ii) If \(C_ 1\) and \(C_ 2\) are distinct members of \({\mathcal C}'\), \(e\in C_ 1\cap C_ 2\), and \(|(C_ 1\cup C_ 2)-e|\leq k\), then \((C_ 1\cup C_ 2)-e\) contains a member of \({\mathcal C}'\). (iii) All members of \({\mathcal C}'\) have at most \(k\) elements. (iv) \(E\) has a \(k\)-element subset that contains no members of \({\mathcal C}'\). This result is then used to characterize when a matroid on \(E\) is uniquely determined by its set of non-spanning circuits.
0 references
non-spanning circuits
0 references
matroid
0 references