Combinatorial Theory
It is now generally recognized that the field of combinatorics has, over the past years, evolved into a fully-fledged branch of discrete mathematics whose potential with respect to computers and the natural sciences is only beginning to be realized. Still
- PDF / 37,471,952 Bytes
- 489 Pages / 481.89 x 691.654 pts Page_size
- 49 Downloads / 427 Views
Editors
S.S. Chern 1.L. Doob 1. Douglas, jr. A. Grothendieck E. Heinz F. Hirzebruch E. Hopf S. Mac Lane W. Magnus M.M. Postnikov W. Schmidt D.S. Scott K. Stein 1. Tits B.L. van der Waerden Managing Editors
B. Eckmann 1.K. Moser
Martin Aigner
Combinatorial Theory
Springer-Verlag Berlin Heidelberg New York
Martin Aigner II. Institut fiir Mathematik Freie Universitat Berlin Konigin-Luise-Strasse 24/26 1000 Berlin 33 Federal Republic of Germany
AMS Subject Classification (1980): 05xx, 06xx
With 123 Figures
Library of Congress Cataloging in Publication Data Aigner, Martin, 1942Combinatorial theory. (Grundlehren der mathematischen Wissenschaften; 234) Bibliography: p. Includes index. \. Combinatorial analysis. I. Title. II. Series: Die Grundlehren der mathematischen Wissenschaften in Einzeldarstellungen; 234) QA164.A36 511'.6 79-1011
All rights reserved. No part of this book may be translated or reproduced in any form without written permission from Springer-Verlag.
© 1979 by Springer-Verlag New York Inc. Softcover reprint of the hardcover 1st edition 1979 9 8 7 6 543 2 1
ISBN 978-1-4615-6668-7 DOl 10.1007/978-1-4615-6666-3
ISBN 978-1-4615-6666-3 (eBook)
Preface
It is now generally recognized that the field of combinatorics has, over the past years, evolved into a fully-fledged branch of discrete mathematics whose potential with respect to computers and the natural sciences is only beginning to be realized. Still, two points seem to bother most authors: The apparent difficulty in defining the scope of combinatorics and the fact that combinatorics seems to consist of a vast variety of more or less unrelated methods and results. As to the scope of the field, there appears to be a growing consensus that combinatorics should be divided into three large parts:
(a) Enumeration, including generating functions, inversion, and calculus of finite differences; (b) Order Theory, including finite posets and lattices, matroids, and existence results such as Hall's and Ramsey's; (c) Configurations, including designs, permutation groups, and coding theory. The present book covers most aspects of parts (a) and (b), but none of (c). The reasons for excluding (c) were twofold. First, there exist several older books on the subject, such as Ryser [1] (which I still think is the most seductive introduction to combinatorics), Hall [2], and more recent ones such as Cameron-Van Lint [1] on groups and designs, and Blake-Mullin [1] on coding theory, whereas no comprehensive book exists on (a) and (b). Second, the vast diversity of types of designs, the very complicated methods usually still needed to prove existence or nonexistence, and, in general, the rapid change this subject is presently undergoing do not favor a thorough treatment at this moment. I have also omitted reference to algorithms of any kind because I feel that presently nothing more can be said in book form about this subject beyond Knuth [1], Lawler [1], and Nijenhuis-Wilf [1]. As to the second point, that of systematizing the definitions, methods, and results i
