MATH Seminar

Title: On the number of cliques in graphs with a forbidden clique minor
Seminar: Combinatorics
Speaker: Fan Wei of Stanford University
Contact: Dwight Duffus, dwight@mathcs.emory.edu
Date: 2016-11-28 at 4:00PM
Venue: MSC W301
Download Flyer
Abstract: 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 Kt minor has at most c(t)n cliques. Wood asked in 2007 if c(t) < ct 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 Kt minor has at most 32t=3+o(t)n cliques. This bound is tight for n ≥4t/3. We use the similiar idea to give an upper bound on the number of cliques in an n-vertex graph with no Kt-subdivision. Easy computation will give an upper bound of 23t+o(t)n; a more careful examination gives an upper bound of 21.48t+o(t)n. We conjecture that the optimal exponential constant is 32/3 as in the case of minors. This is a joint work with Jacob Fox.