The ACO Seminar (2010-2011)

Tools from linear algebra have many striking applications in the study of combinatorial problems. One of the earliest such examples is the theorem of Graham and Pollak. Motivated by a communication problem that arose in connection with data transmission, they proved that the edge set of a complete k-vertex graph cannot be partitioned into disjoint union of less than k-1 complete bipartite graphs.

Motivated by this beautiful theorem, more than 20 years ago, Alon, Saks, and Seymour conjectured that all graphs that are obtained by taking an edge disjoint union of k complete bipartite graphs should have chromatic number at most k+1. In this talk we discuss this well known conjecture and its connections to combinatorial geometry and communication complexity.

Joint work with Benny Sudakov.