Ottawa–Carleton
Discrete Mathematics Group

3 October 2008, 11.30am
FTX 137, U. Ottawa

The Graham–Pollak Theorem says: any edge partitioning of a complete graph on n vertices into complete bipartite graphs requires at least n–1 such bipartite graphs. All known proofs of this simple combinatorial statement use linear algebra in one way or another. It has been a big challenge to find a combinatorial proof of this in the last 3 decades, and many possible extensions have been proved/conjectured to this end.

Among these is a conjecture of Alon-Saks-Seymour which claims: if a graph G is edge partitioned into n–1 complete bipartite graphs then G is n-colourable.

In this talk after some introduction to the problem I will talk about our approach to the problem, which proves the statement for n<=10, and raises many other interesting questions.