Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
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@tx.technion.ac.il Agelos Georgakopoulosz Mathematisches Seminar Universitat Hamburg Bundesstrafie 55 20146 Hamburg Germany georgakopoulos@math.uni-hamburg.de Eli Berger Department of Mathematics Haifa University Israel 31905 berger@cri.haifa.ac.il Philipp Sprussel Mathematisches Seminar Universitaat Hamburg Bundesstrafie 55 20146 Hamburg Germany spruessel@math.uni-hamburg.de 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. I-879-124.6. 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 .
