A Note on Maxflow-Mincut and Homomorphic Equivalence in Matroids
Winfried Hochstättler
and Jaroslav Nešetřil
DOI: 10.1023/A:1011268025029
Abstract
Graph homomorphisms are used to study good characterizations for coloring problems Trans. Amer. Math. Soc. 384 (1996), 1281-1297; Discrete Math. 22 (1978), 287-300). Particularly, the following concept arises in this context: A pair of graphs ( A, B) is called a homomorphism duality if for any graph G either there exists a homomorphism 
: A 
G or there exists a homomorphism 
: G B but not both. In this paper we show that maxflow-mincut duality for matroids can be put into this framework using strong maps as homomorphisms. More precisely, we show that, if C k denotes the circuit of length k + 1, the pairs ( C k , C k + 1) are the only homomorphism dualities in the class of duals of matroids with the strong integer maxflow-mincut property ( Jour. Comb. Theor. Ser.B 23 (1977), 189-222). Furthermore, we prove that for general matroids there is only a trivial homomorphism duality.
: A G or there exists a homomorphism : G B but not both. In this paper we show that maxflow-mincut duality for matroids can be put into this framework using strong maps as homomorphisms. More precisely, we show that, if C k denotes the circuit of length k + 1, the pairs ( C k , C k + 1) are the only homomorphism dualities in the class of duals of matroids with the strong integer maxflow-mincut property ( Jour. Comb. Theor. Ser.B 23 (1977), 189-222). Furthermore, we prove that for general matroids there is only a trivial homomorphism duality.Pages: 295–300
Keywords: matroids; strong maps; homomorphisms; duality; Menger's theorem
Full Text: PDF
References
1. P. Hell, J. Ne\check set\check ril, and X. Zhu, “Duality and polynomial testing of tree homomorphisms,” Trans. Amer. Math. Soc. 384 (1996), 1281-1297.
2. W. Hochst\ddot atter and J. Ne\check set\check ril, “Linear programming duality and morphisms,” Comment. Math. Univ. Carol. 40 (1999), 577-599.
3. P. Komárek, “Some new good characterizations of directed graphs,” Casopis. Pest. Math. 51 (1984), 348-354.
4. A. Lehman, “Ports and matroids,” Notices Amer. Math. Soc. 12 (1965), 342.
5. J. Oxley, Matroid Theory. Oxford University Press, Oxford, 1992.
6. J. Ne\check set\check ril and A. Pultr, “On classes of relations and graphs determined by subobjects and factorobjects,” Discrete Math. 22 (1978), 287-300.
7. P.D. Seymour, “Matroids with the max-flow min-cut property,” Jour. Comb. Theor. Ser.B 23 (1977), 189-222.
8. N. White (Ed.), Theory of Matroids (Encyclopedia of Mathematics and its Applications 26), Cambridge University Press, Cambridge, 1986.
2. W. Hochst\ddot atter and J. Ne\check set\check ril, “Linear programming duality and morphisms,” Comment. Math. Univ. Carol. 40 (1999), 577-599.
3. P. Komárek, “Some new good characterizations of directed graphs,” Casopis. Pest. Math. 51 (1984), 348-354.
4. A. Lehman, “Ports and matroids,” Notices Amer. Math. Soc. 12 (1965), 342.
5. J. Oxley, Matroid Theory. Oxford University Press, Oxford, 1992.
6. J. Ne\check set\check ril and A. Pultr, “On classes of relations and graphs determined by subobjects and factorobjects,” Discrete Math. 22 (1978), 287-300.
7. P.D. Seymour, “Matroids with the max-flow min-cut property,” Jour. Comb. Theor. Ser.B 23 (1977), 189-222.
8. N. White (Ed.), Theory of Matroids (Encyclopedia of Mathematics and its Applications 26), Cambridge University Press, Cambridge, 1986.