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):