比利时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
****************************