Title: Maximal Independent Sets in Graphs
Speaker: Bruce Sagan, DIMACS, Michigan State University
Date: June 28, 2005 12:30 - 2:00 pm
Location: DIMACS Center, CoRE Bldg, Room 301, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
A combinatorial graph G consists of a set V of vertices and a set E of edges between them. For example, V could be a set of cities with an edge between two cities if there is a direct airline flight between them. Graphs are of interest in many disciplines, for example, biology and computer science. An independent set in G is a subset I of the vertex set such that there is no edge between any two vertices in I. Independent sets are crucial in the proof of the famous Four Color Theorem. We will investigate counting maximal independent sets, which are those which are not contained in any larger independent set, starting with a fundamental question of Paul Erdos and Leo Moser.
Joint work with G. Guo, M. Kho, and V. Vatter.