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.

Event Type


Events By Interest


Events By Audience


Department of Mathematics
Add to my calendar

Recent Activity