Duke UG CS Colloquium

Probability Inequalities in the Probabilistic Method on Random Graphs

Speaker:Sandra Batista
Date: Monday, April 3, 2017
Time: 11:45am - 12:45pm
Location: D106 LSRC, Duke
Lunch will be served at 12:45.

Abstract

During this talk we will present two examples of the probabilistic method on random graphs. As an example application of Markov's inequality, we will describe the result of Erdos that there exists a graph of arbitrarily high chromatic number and arbitrarily high girth. As an example application of Chebyshev's inequality and the Second Moment Method, we will examine the clique number in random graphs. Our discussion will rely primarily on tools from an introductory discrete mathematics course. We encourage undergraduates to join our discussion and participate.

Biography

Sandra is a lecturer at Princeton University. She completed her AB in computer science at Harvard University with full scholarship support from the AT&T Engineering Scholarship program. She completed her M.S. and Ph.D. at UCLA in computer science, specializing in complexity theory, with generous fellowship support from the AT&T Labs Fellowship Program. For her postdoctoral work she studied computational genetics and statistical methods at UNC Chapel Hill and Duke University. Her current research focuses on gene expression analysis and statistical methods for large scale data.

Hosted by:
Owen Astrachan