报告题目：Independent transversals in multipartite graphs

报告人：Prof. Yi Zhao（Georgia State University Atlanta, U.S.A.）

时间：6月5日（周四）下午3:00-4:00

地点：理科楼A304

摘要：An independent transversal in a multipartite graph is an independent set that intersects each part in exactly one vertex. We show that given any positive even integer r, every r-partite graph with parts of size n and maximum degree r n / (2r-2) - t (t>0) contains c t n^{r-1}) independent transversals. This is best possible up to the constant c=c_r, confirming a conjecture of Haxell and Szabo from 2006 and partially answering a question Erdos from 1972 and a question of Bollobas, Erdos and Szemeredi from 1975.

We also show that for every s\ge 2, even r\ge 2 and sufficiently large n, every r-partite graph with parts of size n and maximum degree \Delta<r n / (2r-2)- c n^{1-1/s} contains an independent set with exactly s vertices in each part. This is best possible up to the value of c for s=2, 3 due to well-known constructions for the Zarankiewicz problem.

This is a joint work with Yantao Tang.

邀请人：陆玫