| Title:
|
Linear programming duality and morphisms (English) |
| Author:
|
Hochstättler, Winfried |
| Author:
|
Nešetřil, Jaroslav |
| Language:
|
English |
| Journal:
|
Commentationes Mathematicae Universitatis Carolinae |
| ISSN:
|
0010-2628 (print) |
| ISSN:
|
1213-7243 (online) |
| Volume:
|
40 |
| Issue:
|
3 |
| Year:
|
1999 |
| Pages:
|
577-592 |
| . |
| Category:
|
math |
| . |
| Summary:
|
In this paper we investigate a class of problems permitting a good characterisation from the point of view of morphisms of oriented matroids. We prove several morphism-duality theorems for oriented matroids. These generalize LP-duality (in form of Farkas' Lemma) and Minty's Painting Lemma. Moreover, we characterize all morphism duality theorems, thus proving the essential unicity of Farkas' Lemma. This research helped to isolate perhaps the most natural definition of strong maps for oriented matroids. (English) |
| Keyword:
|
oriented matroids |
| Keyword:
|
strong maps |
| Keyword:
|
homomorphisms |
| Keyword:
|
duality |
| MSC:
|
05B35 |
| MSC:
|
05C99 |
| MSC:
|
18B99 |
| MSC:
|
52C40 |
| MSC:
|
90C05 |
| MSC:
|
90C27 |
| MSC:
|
90C46 |
| idZBL:
|
Zbl 1065.05027 |
| idMR:
|
MR1732478 |
| . |
| Date available:
|
2009-01-08T18:55:27Z |
| Last updated:
|
2012-04-30 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/119113 |
| . |
| Reference:
|
[1] Bachem A., Kern W.: Linear Programming Duality: An Introduction to Oriented Matroids.Springer, Berlin etc., 1992. Zbl 0757.90050, MR 1230380 |
| Reference:
|
[2] Bacik R., Mahajan S.: Interactive proof systems and polynomial algorithms.preprint. |
| Reference:
|
[3] Björner A., Las Vergnas M., Sturmfels B., White N., Ziegler G.M.: Oriented Matroids.Encyclopedia of Mathematics and its Applications 46, Cambridge University Press, 1993. MR 1226888 |
| Reference:
|
[4] Bland R.G., Dietrich B.L.: An abstract duality.Discrete Math. 70 (1988), 203-208. Zbl 0686.05014, MR 0949779 |
| Reference:
|
[5] Bland R.G., Las Vergnas M.: Orientability of matroids.J. Combin. Theory Ser. B 24 (1978), 94-123. Zbl 0374.05016, MR 0485461 |
| Reference:
|
[6] Edmonds J.: Paths, trees and flowers.Canadian J. Math. 17 (1965), 449-467. Zbl 0132.20903, MR 0177907 |
| Reference:
|
[7] Farkas G.: Theorie der einfachen Ungleichungen.J. Reine Angew. Math. 124 (1902), 1-27. |
| Reference:
|
[8] Feder T., Vardi M.Y.: Monotone Monadic SNP and Constraint Satisfaction.Proc. 25th ACM STOC 1993, pp.612-622. Zbl 0914.68075 |
| Reference:
|
[9] Folkman J., Lawrence J.: Oriented matroids.J. Combin. Theory Ser. B 25 (1978), 199-236. Zbl 0325.05019, MR 0511992 |
| Reference:
|
[10] Grötschel M., Lovász L., Schrijver A.: The ellipsoid method and its consequences in combinatorial optimization.Combinatorica 1 (1981), 169-197. MR 0625550 |
| Reference:
|
[11] Hell P., Zhu X.: Homomorphisms to oriented paths.Discrete Math. 132 (1994), 107-114. Zbl 0819.05030, MR 1297376 |
| Reference:
|
[12] Hell P., Nešetřil J., Zhu X.: Duality and polynomial testing of tree homomorphisms.Trans. Amer. Math. Soc. 348 (1996), 1281-1297. MR 1333391 |
| Reference:
|
[13] Hell P., Nešetřil J., Zhu X.: Complexity of tree homomorphisms.submitted. |
| Reference:
|
[14] Hochstättler W.: A note on the Weak Zone Theorem.Congressus Numerantium 98 (1993), 95-103. MR 1267343 |
| Reference:
|
[15] Hoffman A.J., Schwartz D.E.: On partitions of partially ordered sets.J. Combin. Theory Ser. B 23 (1977), 3-13. MR 0472547 |
| Reference:
|
[16] Hoffman A.J.: On lattice polyhedra.Proceedings 5th Hungarian Coll. on Combinatorics, North Holland, 1978, pp.593-598. Zbl 0443.05003, MR 0519293 |
| Reference:
|
[17] Komarek P.: Some new good characterizations of directed graphs.Časopis Pěst. Mat. 51 (1984), 348-354. MR 0774277 |
| Reference:
|
[18] Komarek P.: Good characterizations.Thesis, Charles University, Prague, 1983. Zbl 0609.05040 |
| Reference:
|
[19] Lovász L., Schrijver A.: oral communication.. |
| Reference:
|
[20] Minty G.J.: On the axiomatic foundations of the theories of directed linear graphs, electrical networks and network-programming.J. Math. and Mechanics 15 (1966), 485-520. Zbl 0141.21601, MR 0188102 |
| Reference:
|
[21] Nešetřil J., Pultr A.: On classes of relations and graphs determined by subobjects and factorobjects.Discrete Math. 22 (1978), 287-300. MR 0522724 |
| Reference:
|
[22] Nešetřil J.: Theory of Graphs.SNTL, Praha, 1979. |
| Reference:
|
[23] Schrijver A.: Theory of Linear and Integer Programming.Wiley-Interscience, Chichester, 1986. Zbl 0970.90052, MR 0874114 |
| Reference:
|
[24] White N. (editor): Theory of Matroids.Encyclopedia of Mathematics and its Applications 26, Cambridge University Press, 1986. MR 0849389 |
| . |
