# Linear programming duality and morphisms

Winfried Hochstättler; Jaroslav Nešetřil

Commentationes Mathematicae Universitatis Carolinae (1999)

- Volume: 40, Issue: 3, page 577-592
- ISSN: 0010-2628

## Access Full Article

top## Abstract

top## How to cite

topHochstättler, Winfried, and Nešetřil, Jaroslav. "Linear programming duality and morphisms." Commentationes Mathematicae Universitatis Carolinae 40.3 (1999): 577-592. <http://eudml.org/doc/248395>.

@article{Hochstättler1999,

abstract = {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.},

author = {Hochstättler, Winfried, Nešetřil, Jaroslav},

journal = {Commentationes Mathematicae Universitatis Carolinae},

keywords = {oriented matroids; strong maps; homomorphisms; duality; oriented matroid; strong map; homomorphism; duality},

language = {eng},

number = {3},

pages = {577-592},

publisher = {Charles University in Prague, Faculty of Mathematics and Physics},

title = {Linear programming duality and morphisms},

url = {http://eudml.org/doc/248395},

volume = {40},

year = {1999},

}

TY - JOUR

AU - Hochstättler, Winfried

AU - Nešetřil, Jaroslav

TI - Linear programming duality and morphisms

JO - Commentationes Mathematicae Universitatis Carolinae

PY - 1999

PB - Charles University in Prague, Faculty of Mathematics and Physics

VL - 40

IS - 3

SP - 577

EP - 592

AB - 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.

LA - eng

KW - oriented matroids; strong maps; homomorphisms; duality; oriented matroid; strong map; homomorphism; duality

UR - http://eudml.org/doc/248395

ER -

## References

top- Bachem A., Kern W., Linear Programming Duality: An Introduction to Oriented Matroids, Springer, Berlin etc., 1992. Zbl0757.90050MR1230380
- 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. MR1226888
- Bland R.G., Dietrich B.L., An abstract duality, Discrete Math. 70 (1988), 203-208. (1988) Zbl0686.05014MR0949779
- Bland R.G., Las Vergnas M., Orientability of matroids, J. Combin. Theory Ser. B 24 (1978), 94-123. (1978) Zbl0374.05016MR0485461
- Edmonds J., Paths, trees and flowers, Canadian J. Math. 17 (1965), 449-467. (1965) Zbl0132.20903MR0177907
- 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. Zbl0914.68075
- Folkman J., Lawrence J., Oriented matroids, J. Combin. Theory Ser. B 25 (1978), 199-236. (1978) Zbl0325.05019MR0511992
- Grötschel M., Lovász L., Schrijver A., The ellipsoid method and its consequences in combinatorial optimization, Combinatorica 1 (1981), 169-197. (1981) MR0625550
- Hell P., Zhu X., Homomorphisms to oriented paths, Discrete Math. 132 (1994), 107-114. (1994) Zbl0819.05030MR1297376
- Hell P., Nešetřil J., Zhu X., Duality and polynomial testing of tree homomorphisms, Trans. Amer. Math. Soc. 348 (1996), 1281-1297. (1996) MR1333391
- 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) MR1267343
- Hoffman A.J., Schwartz D.E., On partitions of partially ordered sets, J. Combin. Theory Ser. B 23 (1977), 3-13. (1977) MR0472547
- Hoffman A.J., On lattice polyhedra, Proceedings 5th Hungarian Coll. on Combinatorics, North Holland, 1978, pp.593-598. Zbl0443.05003MR0519293
- Komarek P., Some new good characterizations of directed graphs, Časopis Pěst. Mat. 51 (1984), 348-354. (1984) MR0774277
- Komarek P., Good characterizations, Thesis, Charles University, Prague, 1983. Zbl0609.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) Zbl0141.21601MR0188102
- Nešetřil J., Pultr A., On classes of relations and graphs determined by subobjects and factorobjects, Discrete Math. 22 (1978), 287-300. (1978) MR0522724
- Nešetřil J., Theory of Graphs, SNTL, Praha, 1979.
- Schrijver A., Theory of Linear and Integer Programming, Wiley-Interscience, Chichester, 1986. Zbl0970.90052MR0874114
- White N. (editor), Theory of Matroids, Encyclopedia of Mathematics and its Applications 26, Cambridge University Press, 1986. MR0849389

## Citations in EuDML Documents

top## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.