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.

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.