LINEAR ALGEBRA METHODS IN COMBINATORICS

1 LINEAR ALGEBRA METHODSIN COMBINATORICSL aszl o Babai and P eter FranklVersion March 2020 Slight update of Version 2, 1992. c L aszl o Babai and P eter Frankl. 1988, 1992, perhaps to a recognition of the wide applicability of their elementary concepts andtechniques, both COMBINATORICS and LINEAR ALGEBRA have gained increased representation incollege mathematics curricula in recent combinatorial nature of the determinant expansion (and the related difficulty inteaching it) may hint at the plausibility of some link between the two areas. A more profoundconnection, the use of determinants in combinatorial enumeration goes back at least to thework of Kirchhoff in the middle of the 19th century on counting spanning trees in an is much less known, however, that quite apart from the theory of determinants, theelements of the theory of LINEAR spaces has found striking applications to the theory of familiesof finite sets.

2 With a mere knowledge of the concept of LINEAR independence, unexpectedconnections can be made between ALGEBRA and COMBINATORICS , thus greatly enhancing theimpact of each subject on the student s perception of beauty and sense of coherence inmathematics. If these adjectives seem inflated, the reader is kindly invited to open the firstchapter of the book, read the first page to the point where the first result is stated ( Nomore than 32 clubs can be formed in Oddtown ), and try to prove it before reading on. (Theeffect would, of course, be magnified if the title of this volume did not give away where tolook for clues.)What we have said so far may suggest that the best place to present this material is amathematics enhancement program for motivated high school students. While we contendthat parts of the first four chapters could well support such a program, the techniquespresented also provide powerful research tools in COMBINATORICS and related areas such ascombinatorial geometryandtheoretical models of striking example from geometry is the a disproof in the early 1990s of Borsuk s then overhalf-century old, much studied conjecture on decomposingn-dimensional solids of a givendiameter into pieces of smaller diameter.

3 What Borsuk conjectured was thatn+ 1 piecesalways suffice. This conjecture was widely believed to be true; it was verified for variousclasses of solids, including centrally symmetrical ones, and those with a smooth disproof by Kahn and Kalai (1992), to be presented as Theorem in Chapter 5 wasstunning both for its force and for its simplicity. It did not just beat the conjectured boundc L aszl o Babai and P eter Frankl. 1988, 1992, a trifle: it produced an infinite family where the minimum number of pieces grew as anexponential functionof n. Yet the proof took only a page to describe, with reference to acombinatorial result which occupies a central place in this than presenting as many results as possible, we have concentrated on developingtechniques and showing different METHODS to yield different proofs and a variety of gener-alizations to a small set of focal results.

4 The eclectic collection ofexercisesserves to addboth in depth and in breadth to the scope of the book. Many exercises are accompaniedwith Hints ; and full solutions are given in an appendix ( Answers to exercises ) to thoseexercises marked with a diamond ( ). Asteriscs indicate the degree of results are motivated by geometryis a prime target. Appli-cations to thetheory of computingare prominent in several sections (computational learningtheory (Section ), communication complexity theory (Chap. )). But the theory ofcomputing plays a more subtle role in motivating many of the concepts, even though thismay often not be obvious. A brief survey at the end makes some of these connection explicit(Section ).One problem area of cardinal importance to the theory of computing isthe problem of findingexplicit constructionsfor combinatorial and geometric objects whoseexistence is known through probabilistic arguments.

5 Such problems tend to be notoriouslyhard; in the precious few successful attempts on record, METHODS of ALGEBRA and numbertheory have been the winners. In this volume, an explicit Ramsey graph construction (Sec-tions , ) serves as simple illustration of the phenomenon. Some of the much morecomplex examples known to be directly relevant to the theory of computing are mentionedbriefly, along with a number of open problems in this area (Section ).Having said this, naturally, the prime application area of the METHODS presented remainscombinatorics, especially the theory of extremal set systems. We have made an effort tomotivate each combinatorial application area and to give some idea about the alternative(non- LINEAR - ALGEBRA ) approaches to the same have done our best to make all material accessible to undergraduates with some ex-posure to LINEAR ALGEBRA (determinants, matrix multiplication) and a degree of mathematicalmaturity, the onlyprerequisitesto starting on this book.

6 Although the notion offieldsandtheircharacteristicare used throughout, the reader will lose little by taking the term field ofcharacteristicp to be a synonym of the domain{0,1,..,p 1}with operations performedmodulopwherepis a prime number; and the term field of characteristic zero to mean thedomainQof rational numbers orR, the real techniques not normally covered in standard courses (such as affine subspaces,orthogonality in spaces over finite fields, the exterior ALGEBRA , subspaces in general position)are introduced in full detail. An occasional review of the relevant chapters of a text onabstract ALGEBRA or the elements of number theory might be helpful; the review sections ofChapter 2 are specifically intended to guide such an effort to keep prerequisites to a minimum, the size of the volume manageable, and1 Sections and together give a complete and self-contained proof of this surprising c L aszl o Babai and P eter Frankl.

7 1988, 1992, minimize the overlap with existing texts and monographs, we have omitted major areasthat would fit the title of the book. The most painful omission is that of spectral (eigenvalue) METHODS . However, excellent expositions of some of these METHODS are easily accessible forthe more advanced reader (see e. g., in increasing order of demand on the reader, Chapter 11of Lov asz (1979c), Biggs (1974), Godsil (1989), Brouwer, Cohen, Neumaier (1989), Bannai,Ito (1984)).The list of major relevant areas omitted or hardly touched upon in the present volumeincludes spectral techniques in the study of highly regular structures (strongly regular graphs,association schemes, designs, finite geometries); algebraic theory of error correcting codes; spectral techniques in the study of properties of graphs such as connectivity and ex-pansion, diameter, independent sets, chromatic number; finite Markov chains; matroids: a combinatorial model of LINEAR independence; LINEAR programming and combinatorial optimization; lattices and the geometry of numbers ; applications to the design of efficient algorithms.

8 Applications to lower bound, simulation, and randomization techniques in various mod-els of computation and this may look like too long a list to ignore, we feel that the modest material we docover is in areas in the most pressing need of audienceof the text includes undergraduates, graduate students and re-searchers working in discrete mathematics, discrete geometry, the theory of computing, ap-plications of ALGEBRA , as well as open-minded mathematicians irrespective of their specificarea of interest. The text can be used ascourse materialin several ways. First of all, it canbe the text for a one-semester graduate course, providing techniques forresearch levelopenproblems. Some other recipes for classroom use: Use Chapters 1 5 embedded in an introductory course on COMBINATORICS . Use Chapters 5 7 embedded in an advanced course on COMBINATORICS .

9 Present parts of Chapters 1 and 4 as entertaining applications in an introductory courseon LINEAR ALGEBRA . c L aszl o Babai and P eter Frankl. 1988, 1992, Use Chapter 6 to introduce and motivate wedge products. Select material from Chapters 3, 5, and 6 to show delightful applications of the elementsof abstract ALGEBRA . Present thefull proof of the Kahn Kalai Theorem(Sections ) in justtwo classesin a Topics course. Advise students to review their basic abstract and LINEAR ALGEBRA along the outlinegiven in Chapter 2 and parts of Chapter 3. Note that, while these two chapters are in-troductory in character, substantial results appear already in Chapter 3. These includeGale s Theorem on how to distribute points on a sphere evenly, and the resultant proofby B ar any of Kneser s Conjecture on the chromatic number of certain graphs.

10 A puz-zling computational problem, with Jacob Schwartz s amusing Monte Carlo algorithmto solve it, appears in Section material can be used in conjunction with other texts on COMBINATORICS . A combina-tion with one of the following is especially recommended:Ian Anderson, COMBINATORICS of finite sets, Oxford University Press, 1987;B ela Bollob as, COMBINATORICS , Cambridge University Press 1986;or in an advanced seminar with Chapters 8, 9, and 13 ofL aszl o Lov asz,Combinatorial Problems and Exercises, North Holland of the combinations suggested above have been tried out in a variety of coursesettings on audiences of widely varying backgrounds. The presentation of the material isbased on classroom experience gathered by the authors at E otv os University, Budapest; TheUniversity of Chicago; Tokai University, Hiratsuka; and the University of Tokyo.