Title: Independent Sets in Graphs with Given Minimum Degree
Speaker: Jonathan Cutler, Montclair State University
Date: Tuesday, October 1, 2013 2:00pm
Location: Hill Center, Room 525, Rutgers University, Busch Campus, Piscataway, NJ
There has been quite a bit of recent research involving extremal problems for the enumeration of certain graph substructures. For example, Kahn used an entropy method to show that the number of independent sets in a d-regular bipartite graph on n vertices is at most $(2^{d+1}-1)^{n/(2d)}$. Zhao was able to show that this upper bound holds for general regular graphs. Galvin conjectured that if n >= 2d, then the number of independent sets in a graph with n vertices and minimum degree at least d is at most that in $K_{d,n-d}$. Galvin proved that the conjecture is true for a fixed d provided n is large. We were able to prove a strengthened version of Galvin's conjecture, covering the case when n<2d as well. In this talk, we will present the main ideas in the proof of this result. This is joint work with Jamie Radcliffe.
See: http://math.rutgers.edu/seminars/allseminars.php?sem_name=Discrete%20Math