Department of Mathematics,
University of California San Diego
****************************
Math 269 - Combinatorics Seminar
Michael Tait
Carnegie Mellon University (CMU)
On the Tur\'an number of theta graphs
Abstract:
The theta graph $\Theta_{k, t}$ consists of two vertices with $t$ internally disjoint paths of length $k$ between them. Since $\Theta_{k,2}$ is a cycle of length $2k$, the study of the Tur\'an number of this graph includes the notorious even-cycle problem. We show that for fixed $k$ and large $t$, a graph without a $\Theta_{k,t}$ contains at most $c_k t^{1-1/k}n^{1+1/k}$ edges, and we use graphs constructed via random polynomials to show that this is sharp up to the constant $c_k$ when $k$ is odd.
Host: Jacques Verstraete
May 17, 2018
3:00 PM
AP&M 6218
****************************