Event time:

Thursday, April 11, 2019 - 4:00pm

Location:

DL 431

Speaker:

Michael Tait

Speaker affiliation:

Carnegie-Mellon University

Event description:

For a fixed integer $k$ we consider the problem of how many edges may be in an $n$-vertex graph where no pair of vertices have $t$ internally disjoint paths of length $k$ between them. When $t=2$ this is the notorious even cycle problem. We show that such a graph has at most $c_k t^{1-1/k}n^{1+1/k}$ edges, and we use graphs constructed via random polynomials to show that the dependence on $t$ is correct when $k$ is odd.

Research Area(s):