Injective Choice Functions
- PDF / 9,579,811 Bytes
- 189 Pages / 468 x 684 pts Page_size
- 0 Downloads / 199 Views
1238 Michael Holz Klaus-Peter Podewski Karsten Steffens
Injective Choice Functions
Springer-Verlag Berlin Heidelberg New York London Paris Tokyo
Authors
Michael Holz Klaus-Peter Podewski Karsten Steffens Institute of Mathematics, University of Hannover Welfengarten 1, 3000 Hannover, Federal Republic of Germany
Mathematics Subject Classification (1980): 04-02,05-02, 03E05, 04A20, 05A05, 05C70 ISBN 3-540-17221-1 Springer-Verlag Berlin Heidelberg New York ISBN 0-387-17221-1 Springer-Verlag New York Berlin Heidelberg
This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically those of translation, reprinting, re-use of illustrations, broadcasting, reproduction by photocopying machine or similar means, and storage in data banks. Under § 54 at the German Copyright Law where copies are made for other than private use, a tee is payable to "Verwertungsgesellschaft Wort", Munich. 1;; Springer-Verlag Berlin Heidelberg 1987 Printed in Germany
Printing and binding: Druckhaus Beltz, Hemsbach/Bergstr. 2146/3140-543210
Preface
A marriage of a family F of sets is an injective choice function for F. The marriage problem consists in estaLJlishing necessary and sufficient criteria which decide if a family has an injective choice function. First P. Hall formulated his well-known criterion for finite families in 1935. This criterion was generalized by M. Hall to infinite families which have finite members only. A detailed discussion of the results up to 1970 and many applications can be found in Mirsky's book [Mil. In the seventies the research on the marriage problem took a rapid development. Several necessary and sufficient conditions for countable families were found; on the one hand transfinite versions of Hall's Theorem, as for example in [N2], on the other hand extensions of the Compactness Theorem as in [HPS 1]. In Chapter III we are going to present these criteria and show that they are all equivalent. But only three years ago, R. Ah a r o n t , C.St.J.A. Nash-Williams, and S. Shelah published the first necessary and sufficient criterion for arbitrary families. Its form follows the one of P. 's Theorem: a family has a marriage if ·and only if it does not contain one of a set of "forbidden" substructures. Similar criteria can be found in the second chapter of this book. The Aharoni-Nash-Williams-Shelah-criterion. which we obtain as a consequence of a criterion of K.P. Podewski in this book, has been successfully applied by Aharoni to solve some famous problems in graph theory. His main result is the proof of a strong form of Konig's Duality Theorem, suggested by P. Erdos. As a consequence he could prove a strong version of Menger's Theorem for graphs which contain no infinite path. One aim of this book is a self-contained representation of these intricate theorems. For this reason we have inserted a separate chapter on set theory for those readers who are not so familiar with transfinite methods. We suggest reading the introduction after the study of
Data Loading...
