Graph structures and applications

图结构及应用

• 批准号: 1265564
• 负责人: Xingxing Yu
• 金额: $ 16万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2013
• 资助国家: 美国
• 起止时间: 2013-08-01 至 2017-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1265564&HistoricalAwards=false
• 关键词: Graph; structures; applications

Solutions to many problems in graph theory and extremal combinatorics require structural information of graphs and hypergraphs. The PI plans to study graph structures and their potential applications to graph colorings, in particular, a long standing conjecture of Seymour on topological K5. He also plans to work on several problems of Bollobas and Scott about partitions of graphs and hypergraphs. The PI has previously obtained a number of results in the proposed area using structural and extremal methods, and he plans to continue his work.Graph theory studies discrete structures such as networks (e.g., the Internet). Many problems in the real world may be formulated as problems on graphs, and mathematical techniques have been applied to attack such problems. When the structure of a class of graphs is well understood, efficient methods can often be found to solve problems on these graphs. When the structure is not clear, one often tries other mathematical methods (e.g. algebraic and probabilistic methods). This proposal considers both structural and extremal problems in graph theory. Progress on these problems should increase our understanding of graph theory and has potential applications to areas such as optimization and computer science.

图论和极值组合学中的许多问题的解决都需要图和超图的结构信息。PI计划研究图结构及其在图着色中的潜在应用，特别是Seymour关于拓扑K5的长期猜想。 他还计划工作的几个问题的Bollobas和斯科特分区的图形和超图。PI以前已经在建议的领域使用结构和极值方法获得了一些结果，他计划继续他的工作。图论研究离散结构，如网络（例如，互联网）。 真实的世界中的许多问题都可以表述为图上的问题，数学技术已经被应用于解决这些问题。当一类图的结构被很好地理解时，通常可以找到有效的方法来解决这些图上的问题。当结构不清楚时，人们经常尝试其他数学方法（例如代数和概率方法）。该建议考虑了图论中的结构和极值问题。这些问题的进展应该增加我们对图论的理解，并在优化和计算机科学等领域有潜在的应用。