Fakulta matematiky, fyziky
a informatiky
Univerzita Komenského v Bratislave

Seminár z teórie grafov - Fan Wei (9.5.2019)

vo štvrtok 9.5.2019 o 9:50 hod. v miestnosti M/213


07. 05. 2019 13.35 hod.
Od: Martin Škoviera

Prednášajúci: Fan Wei (Stanford Unversity, CA, USA)

Názov: Counting the number of cliques in hereditary minor-closed families of graphs

Termín: 9.5.2019, 9:50 hod., M/213


Abstrakt:
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.