Dept. of Computer Science, University of Chicago, 1992, -225
pp.
Due perhaps to a recognition of the wide applicability of their elementary concepts and techniques, both combinatorics and linear algebra have gained increased representation in college mathematics curricula in recent years. The combinatorial nature of the determinant expansion (and the related difficulty in teaching it) may hint for the plausibility of some link between the two areas. A more profound connection, the use of determinants in combinatorial enumeration goes back at least to the work of Cayley in the last century on counting spanning trees in a network.
It is much less known, however, that quite apart from the theory of determinants, the elements of the theory of linear spaces have striking applications to the theory of families of finite sets. With a mere knowledge of the concept of linear independence, completely unexpected connections can be made between algebra and combinatorics, thus greatly enhancing the impact of each subject on the student's perception of beauty and sense of coherence in mathematics. If these adjectives seem inflated, the reader is kindly invited to open the first chapter of the book, read the first page to the point where the first result is stated ("No more than 32 clubs can be formed in Oddtown"), and try to prove it before reading on. (The effect would, of course, be magnified if the title of this volume did not give away where to look for clues.)
What we have said so far may suggest that the best place to present this material at is a mathematics enhancement program for motivated high school students. While we contend that parts of the first four chapters could well support such a program, the techniques presented provide powerful research tools in combinatorics and related areas such as combinatorial geometry and theoretical models of computation.
A striking example from geometry is the recent disproof of Borsuk's over half-century old, much studied conjecture on decomposing n-dimensional solids of a given diameter into pieces of smaller diameter. What Borsuk conjectured was that n + 1 pieces always suffice. This conjecture was widely believed to be true; it was verified for various classes of solids, including centrally symmetrical ones, and those with a smooth boundary. The disproof by Kahn and Kalai (1992), to be presented as Theorem 5.23 in Chapter 5 was stunning both for its force and for its simplicity. It did not just beat the conjectured bound by a trifle: it produced an infinite family where the minimum number of pieces grew as an exponential function of sqrt(n). Yet the proof took only a page to describe, with reference to a combinatorial result which occupies a central place in this book.
Rather than presenting as many results as possible, we have
concentrated on developing techniques and showing different methods to yield
different proofs and a variety of generalizations to a small set of focal
results. The eclectic collection of exercises serves to add both in depth and
in breadth to the scope of the book. Many exercises are accompanied with
"Hints"; and full solutions are given in an appendix ("Answers to
exercises") to those exercises marked with a diamond (0) Asteriscs indicate
the degree of difficulty.
Most results are motivated by applications. This book is geometry all over. Applications to the theory of computing are prominent in several sections (computational leaing theory (Section 7.4), communication complexity theory (Chap. 10.1)). But the theory of computing plays a more subtle role in motivating many of the concepts, even though this may often not be obvious. A brief survey at the end makes some of these connection explicit (Section 10.2). One problem area of cardinal importance to the theory of computing is the problem of finding explicit constructions for combinatorial and geometric objects whose existence is known through probabilistic arguments. Such problems tend to be notoriously hard; and in the few successful attempts on record, methods of algebra and number theory have been the winners. In this volume, explicit Ramsey graph constructions (Sections 4.2, 5.7) serve as simple illustrations of the phenomenon. Some of the much more complex examples known to be directly relevant to the theory of computing are mentioned briefly, along with a number of open problems in this area (Section 10.2).
Having said all this, naturally, the prime application area of the methods presented remains combinatorics, especially the theory of extremal set systems. We have made an effort to motivate each combinatorial application area and to give some idea about the alteative (non-linear-algebra) approaches to the same area.
We have done our best to make all material accessible to undergraduates with some exposure to linear algebra (determinants, matrix multiplication) and a degree of mathematical maturity, the only prerequisites to starting on this book. Although the notion of fields and their characteristic are used throughout, the reader will lose little by taking the term "field of characteristic p" to be a synonym of the domain {0,l,.,p-1} with operations performed mod ? where ? is a prime number; and the term "field of characteristic zero" to mean the domain Q of rational numbers.
Warm-up.
Basic linear algebra and combinatorics.
"General position" arguments.
Set systems with restricted intersections.
Spaces of polynomials.
Tensor product methods.
A class of higher incidence matrices: the inclusion matrix.
Applications of inclusion matrices.
ally ordered sets.
Applications to the Theory of Computing.
Due perhaps to a recognition of the wide applicability of their elementary concepts and techniques, both combinatorics and linear algebra have gained increased representation in college mathematics curricula in recent years. The combinatorial nature of the determinant expansion (and the related difficulty in teaching it) may hint for the plausibility of some link between the two areas. A more profound connection, the use of determinants in combinatorial enumeration goes back at least to the work of Cayley in the last century on counting spanning trees in a network.
It is much less known, however, that quite apart from the theory of determinants, the elements of the theory of linear spaces have striking applications to the theory of families of finite sets. With a mere knowledge of the concept of linear independence, completely unexpected connections can be made between algebra and combinatorics, thus greatly enhancing the impact of each subject on the student's perception of beauty and sense of coherence in mathematics. If these adjectives seem inflated, the reader is kindly invited to open the first chapter of the book, read the first page to the point where the first result is stated ("No more than 32 clubs can be formed in Oddtown"), and try to prove it before reading on. (The effect would, of course, be magnified if the title of this volume did not give away where to look for clues.)
What we have said so far may suggest that the best place to present this material at is a mathematics enhancement program for motivated high school students. While we contend that parts of the first four chapters could well support such a program, the techniques presented provide powerful research tools in combinatorics and related areas such as combinatorial geometry and theoretical models of computation.
A striking example from geometry is the recent disproof of Borsuk's over half-century old, much studied conjecture on decomposing n-dimensional solids of a given diameter into pieces of smaller diameter. What Borsuk conjectured was that n + 1 pieces always suffice. This conjecture was widely believed to be true; it was verified for various classes of solids, including centrally symmetrical ones, and those with a smooth boundary. The disproof by Kahn and Kalai (1992), to be presented as Theorem 5.23 in Chapter 5 was stunning both for its force and for its simplicity. It did not just beat the conjectured bound by a trifle: it produced an infinite family where the minimum number of pieces grew as an exponential function of sqrt(n). Yet the proof took only a page to describe, with reference to a combinatorial result which occupies a central place in this book.
Rather than presenting as many results as possible, we have
concentrated on developing techniques and showing different methods to yield
different proofs and a variety of generalizations to a small set of focal
results. The eclectic collection of exercises serves to add both in depth and
in breadth to the scope of the book. Many exercises are accompanied with
"Hints"; and full solutions are given in an appendix ("Answers to
exercises") to those exercises marked with a diamond (0) Asteriscs indicate
the degree of difficulty.
Most results are motivated by applications. This book is geometry all over. Applications to the theory of computing are prominent in several sections (computational leaing theory (Section 7.4), communication complexity theory (Chap. 10.1)). But the theory of computing plays a more subtle role in motivating many of the concepts, even though this may often not be obvious. A brief survey at the end makes some of these connection explicit (Section 10.2). One problem area of cardinal importance to the theory of computing is the problem of finding explicit constructions for combinatorial and geometric objects whose existence is known through probabilistic arguments. Such problems tend to be notoriously hard; and in the few successful attempts on record, methods of algebra and number theory have been the winners. In this volume, explicit Ramsey graph constructions (Sections 4.2, 5.7) serve as simple illustrations of the phenomenon. Some of the much more complex examples known to be directly relevant to the theory of computing are mentioned briefly, along with a number of open problems in this area (Section 10.2).
Having said all this, naturally, the prime application area of the methods presented remains combinatorics, especially the theory of extremal set systems. We have made an effort to motivate each combinatorial application area and to give some idea about the alteative (non-linear-algebra) approaches to the same area.
We have done our best to make all material accessible to undergraduates with some exposure to linear algebra (determinants, matrix multiplication) and a degree of mathematical maturity, the only prerequisites to starting on this book. Although the notion of fields and their characteristic are used throughout, the reader will lose little by taking the term "field of characteristic p" to be a synonym of the domain {0,l,.,p-1} with operations performed mod ? where ? is a prime number; and the term "field of characteristic zero" to mean the domain Q of rational numbers.
Warm-up.
Basic linear algebra and combinatorics.
"General position" arguments.
Set systems with restricted intersections.
Spaces of polynomials.
Tensor product methods.
A class of higher incidence matrices: the inclusion matrix.
Applications of inclusion matrices.
ally ordered sets.
Applications to the Theory of Computing.