Title: Extremal counting problems for matchings and independent sets
Speaker: Jeff Kahn, Rutgers University
Date: Wednesday, April 14, 2010 12:10pm
Location: Graduate Student Lounge, 7th Floor, Hill Center, Rutgers University, Busch Campus, Piscataway, NJ
I'll mention one or two theorems, but will mostly focus on open problems. Sample question: how may independent sets can one have in a d-regular graph on n vertices? (An independent set is a set of vertices spanning no edges.) A mildly unifying theme that I'll try and probably fail to get to is the use of entropy in attacking some of these questions.