Linear algebra method in combinatorics

SIAM Student Seminar
Friday, April 10, 2009 - 12:30
2 hours
Skiles 269
School of Mathematics, Georgia Tech
Linear algebra method is a very useful method in combinatorics. Lovas Theorem (a very deep theorem about perfect graph) is proved by using this way. The idea is, if we want to come up with an upper bound on the size of a set of objects, associate them with elements in a vector space V of relatively low dimension, and show that these elements are linearly independent. Then we cannot have more objects in our set than the dimension of V. We will show we can use this way to solve some combinatorics problem, such as odd town problem and two-distance sets problem.