The ACO Seminar (2010-2011)
, 3:30pm, Wean 8220
Alon-Saks-Seymour conjecture and related problems
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.
Back to the ACO home page