Previous |  Up |  Next


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:
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


Files Size Format View
CommentatMathUnivCarolRetro_40-1999-3_17.pdf 266.0Kb application/pdf View/Open
Back to standard record
Partner of
EuDML logo