Linear programming duality and morphisms
Hochstättler, Winfried ; Nešetřil, Jaroslav
Commentationes Mathematicae Universitatis Carolinae, Tome 40 (1999), p. 577-592 / Harvested from Czech Digital Mathematics Library
Access to full text
Full (PDF)

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.

Publié le : 1999-01-01
Classification:  05B35,  05C99,  18B99,  52C40,  90C05,  90C27,  90C46 
@article{119113,
     author = {Winfried Hochst\"attler and Jaroslav Ne\v set\v ril},
     title = {Linear programming duality and morphisms},
     journal = {Commentationes Mathematicae Universitatis Carolinae},
     volume = {40},
     year = {1999},
     pages = {577-592},
     zbl = {1065.05027},
     mrnumber = {1732478},
     language = {en},
     url = {http://dml.mathdoc.fr/item/119113}
}

Hochstättler, Winfried; Nešetřil, Jaroslav. Linear programming duality and morphisms. Commentationes Mathematicae Universitatis Carolinae, Tome 40 (1999) pp. 577-592. http://gdmltest.u-ga.fr/item/119113/

Bachem A.; Kern W. Linear Programming Duality: An Introduction to Oriented Matroids, Springer, Berlin etc., 1992. | MR 1230380 | Zbl 0757.90050

Bacik R.; Mahajan S. Interactive proof systems and polynomial algorithms, preprint.

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

Bland R.G.; Dietrich B.L. An abstract duality, Discrete Math. 70 (1988), 203-208. (1988) | MR 0949779 | Zbl 0686.05014

Bland R.G.; Las Vergnas M. Orientability of matroids, J. Combin. Theory Ser. B 24 (1978), 94-123. (1978) | MR 0485461 | Zbl 0374.05016

Edmonds J. Paths, trees and flowers, Canadian J. Math. 17 (1965), 449-467. (1965) | MR 0177907 | Zbl 0132.20903

Farkas G. Theorie der einfachen Ungleichungen, J. Reine Angew. Math. 124 (1902), 1-27. (1902)

Feder T.; Vardi M.Y. Monotone Monadic SNP and Constraint Satisfaction, Proc. 25th ACM STOC 1993, pp.612-622. | Zbl 0914.68075

Folkman J.; Lawrence J. Oriented matroids, J. Combin. Theory Ser. B 25 (1978), 199-236. (1978) | MR 0511992 | Zbl 0325.05019

Grötschel M.; Lovász L.; Schrijver A. The ellipsoid method and its consequences in combinatorial optimization, Combinatorica 1 (1981), 169-197. (1981) | MR 0625550

Hell P.; Zhu X. Homomorphisms to oriented paths, Discrete Math. 132 (1994), 107-114. (1994) | MR 1297376 | Zbl 0819.05030

Hell P.; Nešetřil J.; Zhu X. Duality and polynomial testing of tree homomorphisms, Trans. Amer. Math. Soc. 348 (1996), 1281-1297. (1996) | MR 1333391

Hell P.; Nešetřil J.; Zhu X. Complexity of tree homomorphisms, submitted.

Hochstättler W. A note on the Weak Zone Theorem, Congressus Numerantium 98 (1993), 95-103. (1993) | MR 1267343

Hoffman A.J.; Schwartz D.E. On partitions of partially ordered sets, J. Combin. Theory Ser. B 23 (1977), 3-13. (1977) | MR 0472547

Hoffman A.J. On lattice polyhedra, Proceedings 5th Hungarian Coll. on Combinatorics, North Holland, 1978, pp.593-598. | MR 0519293 | Zbl 0443.05003

Komarek P. Some new good characterizations of directed graphs, Časopis Pěst. Mat. 51 (1984), 348-354. (1984) | MR 0774277

Komarek P. Good characterizations, Thesis, Charles University, Prague, 1983. | Zbl 0609.05040

Lovász L.; Schrijver A. oral communication, .

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. (1966) | MR 0188102 | Zbl 0141.21601

Nešetřil J.; Pultr A. On classes of relations and graphs determined by subobjects and factorobjects, Discrete Math. 22 (1978), 287-300. (1978) | MR 0522724

Nešetřil J. Theory of Graphs, SNTL, Praha, 1979.

Schrijver A. Theory of Linear and Integer Programming, Wiley-Interscience, Chichester, 1986. | MR 0874114 | Zbl 0970.90052

White N. (Editor) Theory of Matroids, Encyclopedia of Mathematics and its Applications 26, Cambridge University Press, 1986. | MR 0849389