Algebraic Methods in Combinatorics, Fall 2014


Grid on a cubic

When:

Mondays, Wednesdays, Fridays 11:30

Where:

Wean Hall 8201

What:

The applications of algebra to (Hungarian-style) combinatorics are relatively rare, but powerful. This course is devoted to such applications.

We will assume a solid knowledge of linear algebra, and a basic familiarity with groups and rings. Additional algebraic background will be introduced in the course.

Techniques covered include the rank argument, multilinear polynomials, combinatorial Nullstellensatz, Chevalley–Warning theorem, extrapolation arguments, Bezout's theorem.

Applications include Lindström's theorem, Fisher's inequalities, intersection patterns of sets, counting unit-distance graphs, theorems of Radon and Tverberg, explicit constructions of Ramsey graphs, counterexample(s) to Borsuk's conjecture, Shannon capacity of graphs, Cauchy–Davenport theorem and its extensions, regular subgraphs, Berlekamp–Welch algorithm, solutions to the joints problem and to the finite field Kakeya.

Resources:

There are two books devoted to applications of linear algebra to combinatorics.

We will cover mostly material from the former book, but I also highly recommend the latter as a nice bed-time reading.

More resources will be added to this page as the course progresses.

More fun:

More fun can be had at my office hours on Mondays 2:30–3:30pm and Thursdays 9:30–10:30am in Wean 6202 or 6th floor lounge. I am also available by appointment.

Course activities:

There will be regular homeworks.

Students are expected to fully participate in the class. Discussions during the lectures are encouraged.

Lectures:


Back to the homepage
E-mail: