Printable PDF
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

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