Simple linear algebra methods are a surprisingly powerful tool to prove combinatorial results. Some examples of combinatorial theorems with linear algebra proofs are the (weak) [perfect graph theorem](http://mathworld.wolfram.com/PerfectGraphTheorem.html), the [Frankl-Wilson theorem](http://gilkalai.wordpress.com/2009/05/21/extremal-combinatorics-vi-the-frankl-wilson-theorem/), and [Fisher's inequality](http://en.wikipedia.org/wiki/Fisher%27s_inequality).


Are there other good examples?



Linear algebra proofs in combinatorics?
Some other examples are the Erdos-Moser conjecture (see R. Proctor, Solution of two difficult problems with linear algebra, *Amer. Math. Monthly* **89** (1992), 721-734), a few results at
[http://math.mit.edu/~rstan/312/linalg.pdf](http://math.mit.edu/%7Erstan/312/linalg.pdf), and Lovasz's famous result on the Shannon capacity of a 5-cycle and other graphs (*IEEE Trans. Inform. Theory* **25** (1979), 1-7). For a preliminary manuscript of Babai and Frankl on this subject (Linear Algebra Methods in Combinatorics), see [http://people.cs.uchicago.edu/~laci/CLASS/HANDOUTS-COMB/BaFrNew.pdf](http://people.cs.uchicago.edu/%7Elaci/CLASS/HANDOUTS-COMB/BaFrNew.pdf) .


2022 version of Babai & Frankl text: [https://people.cs.uchicago.edu/~laci/babai-frankl-book2022.pdf](https://people.cs.uchicago.edu/%7Elaci/babai-frankl-book2022.pdf)


