Using random polynomials in extremal graph theory

Combinatorics Seminar
Event time: 
Thursday, April 11, 2019 - 4:00pm
DL 431
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):