printable pdf
比利时vs摩洛哥足彩 ,
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

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