The ACO Seminar (2017–2018)

Constructing extremal graphs with a forbidden bipartite subgraph is a notoriously difficult problem in extremal graph theory. For even cycles, all of the known constructions come from algebra and finite geometry. Perhaps the most remarkable constructions are the so-called generalized polygons, which can be described as bipartite graphs of diameter d and girth 2d. These graphs are rare, with nontrivial examples existing for only a handful of values for $d$, and are connected to simple groups of Lie type and their corresponding Lie algebras.

In 1986, Vasily Ustimenko gave the first description of these graphs as having vectors from a Lie algebra as vertices, with adjacency defined by a Lie product of zero. This yields a representation of these graphs as vectors in a vector space over a finite field, with adjacency determined by a system of equations. By experimenting with this description, Ustimenko, Lazebnik and Woldar were able to generalize these graphs, discovering a family of graphs with increasing girth, called D(k,q), which to date give the best constructions of cycle-free graphs for cycles of length at least 16.

This two part talk outlines continuation of this work, using Lie algebras to generate graphs with interesting structure. The first part will give some necessary background on Lie algebras, and focus on families of graphs from Kac-Moody algebras which the speaker and Terlep used to give lower bounds on extremal fourteen-cycle free graphs. The second part will discuss open problems and explore higher dimensional analogues of these constructions.

Before the talk, at 3:10pm, there will be tea and cookies in Wean 6220.