Math 582 GB: Algebraic Methods in Combinatorics

Isabella Novik

Winter 2002, MWF 2:30-3:20

---

Methods from Linear Algebra and basic Abstract Algebra provide simple yet very powerful research tools in Combinatorics, especially in the theory of families of finite sets and related areas, such as combinatorial geometry and theory of computing. (Here are several examples: What is the maximum number of points in a two-distance set in Rⁿ? Can you dissect a regular simplex by a finite number of plane cuts and put the pieces together to form a cube?) Among culminations of Linear Algebra methods in combinatorics is a recent disproof of Borsuk’s conjecture (which was open for about 60 years!)

In the class we will study several of such techniques, namely:

• Spaces of polynomials,
• Incidence and higher incidence matrices,
• Tensor product methods;

and their applications, among them

• The Ray-Chaudhuri-Wilson theorem, which provides upper bounds on a size of families of sets with restricted intersections,
• Bollobás-type theorems,
• The edge-reconstruction problem for graphs,
• The recent disproof of Borsuk’s conjecture,
• Radon’s and Tverberg’s theorems.

I will follow to some extent the “Linear Algebra methods in Combinatorics with applications to Geometry and Computer Science” by L. Babai and P. Frankl (Preliminary versions 2, September 1992), and possibly some research papers.