Pure Math Grad Student Seminar (PuMaGraSS)
Friday, October 12, 2018 at 12:00pm to 1:00pm
Speaker: Jonathan Tidor
Title: Graph Property Testing
Abstract: Suppose you are given a very large graph---so large that even reading all of it would be impractical. Is it possible to determine if the graph satisfies some property by only sampling a small subset of the graph?
In this talk we will discuss exactly what this problem means and look at it in a couple different cases: containing a cycle of length four, containing a triangle, and being an expander. Along the way we will discuss connections to other parts of combinatorics.