题  目：Decomposition of random graphs into complete bipartite graphs

报告人：Xing Peng （UCSD）

时   间：2014年1月6日    下午4:30－5:30

地   点：东区管理科研楼  365英国上市官网1208室

摘   要：
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.   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 will prove upper and lower bounds for $G(n, p)$ which gives support for Erd/H{o}s' conjecture.  Also, we will talk about related problems. Joint work with Fan Chung.

主办单位： 365英国上市官网 
         中科院吴文俊数学重点实验室
 
欢迎广大师生参加！