Dec. 2, 3:30pm, Wean 8220

Hao Huang, UCLA

Alon-Saks-Seymour conjecture and related problems

Hao Huang, UCLA

Alon-Saks-Seymour conjecture and related problems

Abstract:

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.