Colored matroid: Difference between revisions
Content deleted Content added
Add detail. Simplify reference format. |
Added free to read link in citations with OAbot #oabot |
||
| (10 intermediate revisions by 4 users not shown) | |||
| Line 1: | Line 1: | ||
{{Short description|Abstract structure with colored elements}} |
|||
In [[mathematics]], a '''colored matroid''' is a [[matroid]] whose elements are labeled from a set of |
In [[mathematics]], a '''colored matroid''' is a [[matroid]] whose elements are labeled from a set of colors, which can be any set that suits the purpose, for instance the set of the first ''n'' positive integers, or the sign set {+, −}. |
||
The interest in colored matroids is through their invariants, especially the |
The interest in colored matroids is through their invariants, especially the colored [[Tutte polynomial]],<ref>{{citation |
||
| last = Zaslavsky | first = Thomas |
|||
| doi = 10.2307/2153985 |
|||
| issue = 1 |
|||
| journal = Transactions of the American Mathematical Society |
|||
| mr = 1080738 |
|||
| pages = 317–347 |
|||
| title = Strong Tutte functions of matroids and graphs |
|||
| volume = 334 |
|||
| year = 1992| jstor = 2153985 |
|||
| doi-access = free |
|||
}}.</ref> which generalizes the Tutte polynomial of a [[signed graph]] of {{harvtxt|Kauffman|1989}}.<ref>{{citation |
|||
| last = Kauffman | first = Louis H. |
|||
| doi = 10.1016/0166-218X(89)90049-8 |
|||
| issue = 1–2 |
|||
| journal = Discrete Applied Mathematics |
|||
| mr = 1031266 |
|||
| pages = 105–127 |
|||
| title = A Tutte polynomial for signed graphs |
|||
| volume = 25 |
|||
| year = 1989| doi-access = free |
|||
| citeseerx = 10.1.1.183.2851 |
|||
}}.</ref> |
|||
There has also been study of optimization problems on matroids where the objective function of the optimization depends on the set of colors chosen as part of a matroid basis.<ref>{{citation |
|||
| ⚫ | |||
| last1 = Maffioli | first1 = Francesco |
|||
| last2 = Rizzi | first2 = Romeo |
|||
| last3 = Benati | first3 = Stefano |
|||
| doi = 10.1016/j.dam.2007.04.015 |
|||
| issue = 15 |
|||
| journal = Discrete Applied Mathematics |
|||
| mr = 2351979 |
|||
| pages = 1958–1970 |
|||
| title = Least and most colored bases |
|||
| volume = 155 |
|||
| year = 2007| doi-access = free |
|||
}}.</ref> |
|||
==See also== |
|||
*L.H. Kauffman (1989). A Tutte polynomial for signed graphs. ''Discrete Applied Mathematics'', Vol. 25, pp.105-127. |
|||
*[[Bipartite matroid]] |
|||
*[[Rota's basis conjecture]] |
|||
| ⚫ | |||
{{reflist}} |
|||
[[Category:Matroid theory]] |
[[Category:Matroid theory]] |
||
{{Combin-stub}} |
|||
Latest revision as of 20:09, 19 December 2023
In mathematics, a colored matroid is a matroid whose elements are labeled from a set of colors, which can be any set that suits the purpose, for instance the set of the first n positive integers, or the sign set {+, −}.
The interest in colored matroids is through their invariants, especially the colored Tutte polynomial,[1] which generalizes the Tutte polynomial of a signed graph of Kauffman (1989).[2]
There has also been study of optimization problems on matroids where the objective function of the optimization depends on the set of colors chosen as part of a matroid basis.[3]
See also
[edit]References
[edit]- ^ Zaslavsky, Thomas (1992), "Strong Tutte functions of matroids and graphs", Transactions of the American Mathematical Society, 334 (1): 317–347, doi:10.2307/2153985, JSTOR 2153985, MR 1080738.
- ^ Kauffman, Louis H. (1989), "A Tutte polynomial for signed graphs", Discrete Applied Mathematics, 25 (1–2): 105–127, CiteSeerX 10.1.1.183.2851, doi:10.1016/0166-218X(89)90049-8, MR 1031266.
- ^ Maffioli, Francesco; Rizzi, Romeo; Benati, Stefano (2007), "Least and most colored bases", Discrete Applied Mathematics, 155 (15): 1958–1970, doi:10.1016/j.dam.2007.04.015, MR 2351979.
.svg){kind=small} | This combinatorics-related article is a stub. You can help Wikipedia by expanding it. |