##### Department of Mathematics,

University of California San Diego

****************************

### Math 269 - Combinatorics

## Hao Huang

#### University of California, Los Angeles

## A counterexample to the Alon-Saks-Seymour conjecture and related problems

##### Abstract:

Consider a graph obtained by taking an edge disjoint union of $k$ complete bipartite graphs, Alon, Saks, and Seymour conjectured that such graphs have chromatic number at most k+1. This well known conjecture remained open for almost twenty years. In this talk, we will show a counterexample to this conjecture. This construction will also lead to some related results in combinatorial geometry and communication complexity. In particular, it implies a nontrivial lower bound of the non-deterministic communication complexity of the ``clique versus independent set'' problem.\\ Joint work with Benny Sudakov.

Host: Jacques Verstraete

### May 18, 2010

### 2:00 PM

### AP&M 7321

****************************