Mathematical Sciences: Algebraic Constructions in Extremal Graph Theory

点击翻译按钮获取中文摘要

Woldar, Lazebnik 9622091 It is often very difficult to construct families of graphs of large girth, which simultaneously possess other quantitative properties such as large size (many edges), small order (few vertices), small diameter, or large expansion. Very often the most important constructions come from other areas of mathematics; e.g., number theory, algebra, geometry, or design theory. This award supports an investigation based on the development and application of algebraic techniques to investigate certain problems in extremal graph theory. These techniques involve the theory of groups, group geometries, affine root systems, and supplemented with novel geometric and combinatorial ideas, have already resulted in some of the best-known constructions in extremal graph theory. The investigators believe that the full potential of these methods has only begun to be realized. The objectives of this investigation include the following: (1) constructing graphs of largest known size subject to having large girth, (2) constructing graphs of smallest known order having large girth, (3) improving the upper bounds for the order of cages, (4) constructing graphs of large girth and small diameter, and (5) constructing families of expanders--perhaps Ramanujan graphs. This research is in the general area of Combinatorics. One of the goals of Combinatorics is to find efficient methods to study how discrete collections of objects can be arranged and what relations among the objects are possible. The behavior of discrete systems is extremely important to modern communications. For example, the design of large networks, such as those occurring in telephone systems, and the design of algorithms in computer science deal with discrete sets of objects, and this makes use of combinatorial research.