Printable PDF
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

****************************