| COMPUTER SCIENCE/DISCRETE MATH I | |
| Topic: | Large Induced Trees in $K_r$-Free Graphs |
| Speaker: | Jacob Fox |
| Affiliation: | Princeton University |
| Date: | Monday, November 24 |
| Time/Room: | 11:15am - 12:15pm/S-101 |
For a graph G , let t(G) denote the maximum number of vertices in an induced subgraph of G that is a tree. We study the problem of bounding t(G) for graphs which do not contain a complete graph K_r on r vertices. This problem was posed twenty years ago by Erdos, Saks, and Sos. Substantially improving earlier results of various researchers, we prove that every connected triangle-free graph on n vertices contains an induced tree of order n^{1/2}. When r > 3, we also show that t(G) > (log n)/(4 log r) for every connected K_r-free graph G of order n. Both of these bounds are tight up to small multiplicative constants, and the first one disproves a recent conjecture of Matousek and Samal.
Joint work with Po-Shen Loh and Benny Sudakov.