Mathematical Sciences: Algebraic Constructions in Extremal Graph Theory

数学科学：极值图论中的代数构造

• 批准号: 9622091
• 负责人: Andrew Woldar
• 金额: $ 12.9万
• 依托单位: Villanova University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1996
• 资助国家: 美国
• 起止时间: 1996-08-15 至 2000-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9622091&HistoricalAwards=false
• 关键词: Mathematical; Sciences; Algebraic; Constructions; Extremal

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.

构造大周长的图族通常是非常困难的，这些图族同时具有其他定量性质，如大尺寸（多边）、小顺序（少顶点）、小直径或大扩展。通常最重要的构造来自数学的其他领域；例如，数论、代数、几何或设计理论。该奖项支持基于代数技术的发展和应用的研究，以研究极值图论中的某些问题。这些技术涉及群理论、群几何、仿射根系统，并辅以新颖的几何和组合思想，已经产生了极值图论中一些最著名的结构。研究人员认为，这些方法的全部潜力才刚刚开始实现。本研究的目标包括以下内容：(1)构造具有大周长的已知最大尺寸的图，(2)构造具有大周长的已知最小阶图，(3)改进笼级的上界，(4)构造大周长和小直径的图，以及(5)构造膨胀器族——可能是Ramanujan图。这项研究属于组合学的一般领域。组合学的目标之一是寻找有效的方法来研究离散的对象集合如何排列以及对象之间可能存在的关系。离散系统的行为对现代通信极为重要。例如，大型网络的设计，比如那些出现在电话系统中的网络，以及计算机科学中处理离散对象集的算法设计，这就利用了组合研究。