|
Department of Mathematical Sciences
Events
People
Colloquia and Seminars
Conferences
Centers
Positions
Areas of Research
About the Department
Alumni |
Algorithms, Combinatorics and Optimization Seminar
University of Wyoming Title: Constructions of cycle-free graphs from Lie algebras, Part 1 Abstract: 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. |
