网站首页  |  实验室概况  |  研究团队  |  新闻中心  |  学术交流  |  学术报告  |  实验室年报  |  联系我们

 
 
  当前位置:首页 -> 学术报告
吴文俊数学重点实验室组合图论系列讲座之一百零二【Fan Wei】
Title: On the number of cliques in graphs with a forbidden clique minor

Speaker:Fan Wei, Stanford University, USA

Time:6.2 10:00-11:00

Place:1518

Abstract:
Reed and Wood and independently Norine, Seymour, Thomas, and Wollan showed that for each $t$ there is $c(t)$ such that every graph on $n$ vertices with no $K_t$ minor has at most $c(t)n$ cliques. Wood asked in 2007 if $c(t)<c^t$ for some absolute constant $c$. This problem was recently solved by Lee and Oum. In this paper, we determine the exponential constant. We prove that every graph on $n$ vertices with no $K_t$ minor has at most $3^{2t/3+o(t)}n$ cliques. This bound is tight for $n \geq 4t/3$.

We use the similiar idea to give an upper bound on the number of cliques in an $n$-vertex graph with no $K_t$-subdivsion. Easy computation will give an upper bound of $2^{3t+o(t)}n$; a more careful examination gives an upper bound of $2^{1.48t+o(t)}n$. We conjecture that the optimal exponential constant is $3^{2/3}$ as in the case of minors.

This is a joint work with Jacob Fox.   
中国科学院吴文俊数学重点实验室