Издательство Chapman and Hall, 1980, -160 pp.
Combinatorics may very loosely be described as that branch of mathematics which is conceed with the problems of arranging objects in accordance with various imposed constraints. It covers a wide range of ideas and because of its fundamental nature it has applications throughout mathematics. Among the well-established areas of combinatorics may now be included the studies of graphs and networks, block designs, games, transversals, and enumeration problems conceing permutations and combinations, from which the subject eaed its title, as well as the theory of independence spaces (or matroids). Along this broad front, various central themes link together the very diverse ideas. The theme which we introduce in this book is that of the abstract concept of independence. Here the reason for the abstraction is to unify; and, as we shall see, this unification pays off handsomely with applications and illuminating sidelights in a wide variety of combinatorial situations.
The study of combinatorics in general, and independence theory in particular, accounts for a considerable amount of space in the mathematical jouals. For the most part, however, the books on abstract independence so far written are at an advanced level, 'whereas the purpose of our short book is to provide an elementary introduction to the subject. It is intended primarily as a text book for undergraduates or as a basis of a postgraduate course and, within its limited compass, we have tried to present the basic notions and to describe just a few of the varied applications of this very attractive branch of mathematics.
We have deliberately chosen to use the term 'independence space', rather than 'matroid' or 'pre-geometry', because we feel that it is the most descriptive label and, therefore, that it has the most universal appeal.
Chapter 1 is conceed with preliminaries and, in particular, it includes two standard forms of independence in a vector space which motivate our abstraction in Chapter 2, where independence spaces are defined. Here various properties of these spaces are described as well as some of the ways in which they may be generated, for example by 'submodular' functions. In Chapter 3 we introduce some clas .ic realizations of independence spaces in graph theory, and we see these two branches of combinatorics each enhancing the other. We meet yet more surprising and beautiful occurrences of independence in Chapter 4, which is devoted to transversal theory. One of our motivations for independence spaces was by means of linear independence in a vector space and, in Chapter 5, we briefly review the problem of the extent to which abstract independence provides a true generalization of linear independence.
As we have already emphasized, this is an elementary and introductory book on independence spaces, and the ninety or so exercises at the ends of the chapters form an integral part of it. These vary in complexity quite considerably, from the routine ones to those which are technically difficult (and are starred). Notes on the exercises and full solutions of most of them are to be found at the end of the book. The pre-requisites for reading this text are fairly minimal: we assume a certain familiarity with the language and algebra of sets and with the usual basic concepts of linear algebra, together with that degree of 'mathematical maturity' normally to be expected of, at any rate, second- and third-year undergraduates in our universities and polytechnics.
The interested reader may wish to use some of the more advanced books cited in the booklist on page 139, for example to trace the origins of the subject in further detail; for, except for the one or two most famous theorems, we have not attributed any results to their originators. Inevitably, a short account such as this can only outline the subject, but we hope that we have provided a foundation which is both interesting in its own right and at the same time a suitable starting point for the more ambitious reader.
Preliminaries.
ndependence spaces.
Graphic spaces.
Transversal spaces.
Appendix on representability.
Combinatorics may very loosely be described as that branch of mathematics which is conceed with the problems of arranging objects in accordance with various imposed constraints. It covers a wide range of ideas and because of its fundamental nature it has applications throughout mathematics. Among the well-established areas of combinatorics may now be included the studies of graphs and networks, block designs, games, transversals, and enumeration problems conceing permutations and combinations, from which the subject eaed its title, as well as the theory of independence spaces (or matroids). Along this broad front, various central themes link together the very diverse ideas. The theme which we introduce in this book is that of the abstract concept of independence. Here the reason for the abstraction is to unify; and, as we shall see, this unification pays off handsomely with applications and illuminating sidelights in a wide variety of combinatorial situations.
The study of combinatorics in general, and independence theory in particular, accounts for a considerable amount of space in the mathematical jouals. For the most part, however, the books on abstract independence so far written are at an advanced level, 'whereas the purpose of our short book is to provide an elementary introduction to the subject. It is intended primarily as a text book for undergraduates or as a basis of a postgraduate course and, within its limited compass, we have tried to present the basic notions and to describe just a few of the varied applications of this very attractive branch of mathematics.
We have deliberately chosen to use the term 'independence space', rather than 'matroid' or 'pre-geometry', because we feel that it is the most descriptive label and, therefore, that it has the most universal appeal.
Chapter 1 is conceed with preliminaries and, in particular, it includes two standard forms of independence in a vector space which motivate our abstraction in Chapter 2, where independence spaces are defined. Here various properties of these spaces are described as well as some of the ways in which they may be generated, for example by 'submodular' functions. In Chapter 3 we introduce some clas .ic realizations of independence spaces in graph theory, and we see these two branches of combinatorics each enhancing the other. We meet yet more surprising and beautiful occurrences of independence in Chapter 4, which is devoted to transversal theory. One of our motivations for independence spaces was by means of linear independence in a vector space and, in Chapter 5, we briefly review the problem of the extent to which abstract independence provides a true generalization of linear independence.
As we have already emphasized, this is an elementary and introductory book on independence spaces, and the ninety or so exercises at the ends of the chapters form an integral part of it. These vary in complexity quite considerably, from the routine ones to those which are technically difficult (and are starred). Notes on the exercises and full solutions of most of them are to be found at the end of the book. The pre-requisites for reading this text are fairly minimal: we assume a certain familiarity with the language and algebra of sets and with the usual basic concepts of linear algebra, together with that degree of 'mathematical maturity' normally to be expected of, at any rate, second- and third-year undergraduates in our universities and polytechnics.
The interested reader may wish to use some of the more advanced books cited in the booklist on page 139, for example to trace the origins of the subject in further detail; for, except for the one or two most famous theorems, we have not attributed any results to their originators. Inevitably, a short account such as this can only outline the subject, but we hope that we have provided a foundation which is both interesting in its own right and at the same time a suitable starting point for the more ambitious reader.
Preliminaries.
ndependence spaces.
Graphic spaces.
Transversal spaces.
Appendix on representability.