##### Department of Mathematics,

University of California San Diego

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

### Math 269 - Combinatorics

## Stefaan de Winter

#### Ghent University (Belgium)

## Projective Planes and $C_4$-free graphs that maximize the number of six cycles.

##### Abstract:

It is a classical problem in graph theory to look for those graphs that maximize the number of copies of a subgraph H and are F-free; the Turan problem being the most well known example of such problem. In this talk I will explain how the incidence graphs of projective planes of order $n$ are exactly those $n$ by $n$ bipartite graphs that are $C_4$-free and maximize the number of eight cycles. An analogous characterization of projective planes as $C_4$-free graphs that maximize the number of six cycles was previously known. I will also explain how a more general conjectural characterization of (the incidence graphs of) projective planes relates to some interesting geometric questions on projective planes. Finally I will mention some related open problems concerning so-called generalized polygons.

### February 17, 2009

### 3:00 PM

### AP&M 7321

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