LINEAR ALGEBRA METHODS IN COMBINATORICS

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.

theory have been the winners. In this volume, an explicit Ramsey graph construction (Sec-tions 4.2, 5.7) serves as simple illustration of the phenomenon. Some of the much more complex examples known to be directly relevant to the theory of computing are mentioned brie y, along with a number of open problems in this area (Section 10.2).

Loading..

Tags:

  Linear, Theory, Graph

Information

Related search queries