Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Strongly maximal matchings in infinite weighted graphs. | Strongly maximal matchings in infinite weighted graphs Ron Aharoni Department of Mathematics Technion Haifa Israel 32000 ra@ Agelos Georgakopoulosz Mathematisches Seminar Universitat Hamburg Bundesstrafie 55 20146 Hamburg Germany georgakopoulos@ Eli Berger Department of Mathematics Haifa University Israel 31905 berger@ Philipp Sprussel Mathematisches Seminar Universitaat Hamburg Bundesstrafie 55 20146 Hamburg Germany spruessel@ Submitted Feb 16 2008 Accepted Oct 20 2008 Published Oct 29 2008 Mathematics Subject Classification 05C70 Abstract Given an assignment of weights w to the edges of an infinite graph G a matching M in G is called strongly w-maximal if for any matching N there holds 52 w e I e 2 N M 52 w e I e 2 M N . We prove that if w assumes only finitely many values all of which are rational then G has a strongly w-maximal matching. This result is best possible in the sense that if we allow irrational values or infinitely many values then there need not be a strongly w-maximal matching. 1 introduction Infinite min-max theorems are rather weak when stated in terms of cardinalities. Cardinalities are too crude a measure to capture the duality relationship. To exemplify this point consider Menger s theorem the first combinatorial theorem that was cast in the form of a min-max equality. Formulated in terms of cardinalities it states that given two The research of the first author was supported by grant no. 780-04 of the Israel Science Foundation by the Technion s research promotion fund a BSF grant and by the Discont Bank chair. yThe research of the second author was supported by a BSF grant zThe research of the first third and fourth authors was supported by GIF grant no. . THE ELECTRONIC JOURNAL OF COMBINATORICS 15 2008 R136 1 sets A and B in an infinite graph the maximal cardinality K of a family of disjoint A-B paths is equal to the minimal cardinality of a vertex-set .
