##### Department of Mathematics,

University of California San Diego

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

### Math 269 - Combinatorics

## Xing Peng

#### UCSD

## Decomposition of random graphs into complete bipartite graphs

##### Abstract:

For a graph $G$, the bipartition number $\tau(G)$ is the minimum number of complete bipartite subgraphs whose edge sets partition the edge set of $G$. In 1971, Graham and Pollak proved that $\tau(K_n)=n-1$. Since then, there have been a number of short proofs for Graham-Pollak theorem by using linear algebra or by using matrix enumeration. We present a purely combinatorial proof for Graham-Pollak theorem. For a graph $G$ with $n$ vertices, one can show $\tau(G) \leq n- \alpha(G)$ easily, where $\alpha(G)$ is the independence number of $G$. Erd\H{o}s conjectured that almost all graphs $G$ satisfy $\tau(G)=n-\alpha(G)$. In this talk, we prove upper and lower bounds for $G(n,p)$ which gives support for Erd\H{o}s' conjecture. Joint work with Fan Chung.

Host: Jeff Remmel

### October 15, 2013

### 4:00 PM

### AP&M 7321

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