Seminar of Graph Theory - Fan Wei (9.5.2019)

Thursday 9.5.2019 at 9:50, Lecture room M/213

---

Fan Wei (Stanford Unversity, CA, USA):
Counting the number of cliques in hereditary minor-closed families of graphs

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$. The method and result can generalize to any minor-closed family of graphs.

We use the similar 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.

---