printable pdf
比利时vs摩洛哥足彩 ,
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

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