- Start Date:
June 28, 2005
- Event Start Time:
12:30 PM
- Event End Time:
1:30 PM
- Organizers:
Christine Agnese
- Seminar Series:
REU Seminar
- Presenter(s):
Bruce Sagan - Michigan State University
- Event Location:
CoRE 301
- 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.
