##### Department of Mathematics,

University of California San Diego

****************************

### Combinatorics Seminar

## Andre Kundgen

#### California State University, San Marcos

## Graphs with many maximum independent sets

##### Abstract:

A graph with independence number alpha is called (alpha,k)-balanced if every induced subgraph on k vertices has independence number alpha as well. We will discuss the maximum number of vertices in an (alpha,k)-balanced graph for fixed k and alpha, a problem with obvious connections to Ramsey Theory. We focus specifically on the case k=2alpha which is motivated from polyhedral combinatorics. (Joint work with A. Brieden, Z. Furedi and R. Ramamurthi)

Host: Fan Chung Graham

### September 7, 2007

### 11:00 AM

### AP&M 7321

****************************