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.
CAGE: Philadelphia Area Combinatorics and Alg. Geometry Seminar
Thursday, May 3, 2018 - 3:00pm
Michael Tait
Carnegie Mellon University