Extremal Combinatorics under Degree Conditions

度数条件下的极值组合

• 批准号: 1700622
• 负责人: Yi Zhao
• 金额: $ 15万
• 依托单位: Georgia State University Research Foundation, Inc.
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2017
• 资助国家: 美国
• 起止时间: 2017-08-01 至 2021-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1700622&HistoricalAwards=false
• 关键词: Extremal; Combinatorics; under; Degree; Conditions

Extremal combinatorics is a central area of combinatorics and has experienced an impressive growth in recent few decades. It deals with the problems of finding the maximum or minimum value of a function over a class of finite objects. Such problems are often related to other branches of mathematics and other fields of science, including biology, chemistry, computer science, information and coding theory. Classical extremal problems, such as Sperner's theorem and Turan's theorem, consider the size of a set system or graph. On the other hand, results such as Dirac's theorem on Hamilton cycles and the Hajnal-Szemeredi theorem, consider the minimum or maximum degree of a graph. The proposed research considers degree versions of several classical results in extremal set theory, including the Erdos-Ko-Rado theorem and the Kruskal-Katona theorem. An obvious difficulty towards solving these problems is that the shifting method, an important tool in extremal set theory, can not be applied. The project also considers degree versions of two well-known difficult problems in extremal (hyper)graph theory: the clique density problem and hypergraph Turan problem. Lastly, extending Dirac's theorem to hypergraphs has attracted much attention in recent years, and the PI will continue his research on this topic. The tools that the PI will apply to attack these problems include the algebraic method, probabilistic method, flag algebra method, absorbing method, and regularity method.

极值组合学是组合学的一个核心领域，近几十年来有了长足的发展。 它处理的问题，找到最大值或最小值的函数在一类有限对象。这类问题通常与数学的其他分支和其他科学领域有关，包括生物学、化学、计算机科学、信息和编码理论。经典的极值问题，如Sperner定理和Turan定理，考虑的是集合系统或图的大小。另一方面，结果，如狄拉克定理的汉密尔顿圈和Hajnal-Szemeredi定理，考虑最小或最大程度的一个图。该研究考虑了极值集理论中几个经典结果的度版本，包括Erdos-Ko-Rado定理和Kruskal-Katona定理。解决这些问题的一个明显困难是极值集理论中的重要工具--移位法不能应用。该项目还考虑了极端（超图）理论中两个著名难题的度版本：团密度问题和超图图兰问题。最后，将狄拉克定理推广到超图的研究近年来引起了人们的广泛关注，PI将继续这方面的研究。PI将用于攻击这些问题的工具包括代数方法，概率方法，标志代数方法，吸收方法和正则性方法。

项目成果

Codegree Conditions for Tiling Complete k-Partite k-Graphs and Loose Cycles

• DOI: 10.1017/s096354831900021x
• 发表时间: 2016-12
• 期刊: Combinatorics, Probability and Computing
• 作者: Wei Gao;Jie Han;Yi Zhao

Tiling Tripartite Graphs with 3-Colorable Graphs: The Extreme Case

用三色图平铺三部分图：极端情况

• DOI: 10.1007/s00373-018-1929-1
• 发表时间: 2018
• 期刊: Graphs and Combinatorics
• 影响因子: 0.7
• 作者: Hogenson, Kirsten;Martin, Ryan R.;Zhao, Yi
• 通讯作者: Zhao, Yi

Codegree Turán Density of Complete $r$-Uniform Hypergraphs

完全$r$-均匀超图的度图兰密度

• DOI: 10.1137/18m1163956
• 发表时间: 2018
• 期刊: SIAM Journal on Discrete Mathematics
• 影响因子: 0.8
• 作者: Lo, Allan;Zhao, Yi
• 通讯作者: Zhao, Yi

Triangle-degrees in graphs and tetrahedron coverings in 3-graphs

图中的三角度和三图中的四面体覆盖

• DOI: 10.1017/s0963548320000061
• 发表时间: 2021
• 期刊: Probability and Computing
• 作者: Falgas-Ravry, Victor;Markström, Klas;Zhao, Yi
• 通讯作者: Zhao, Yi

Hamiltonicity in randomly perturbed hypergraphs

随机扰动超图中的哈密顿性

• DOI: 10.1016/j.jctb.2019.12.005
• 发表时间: 2020
• 期刊: Series B
• 作者: Han, Jie;Zhao, Yi
• 通讯作者: Zhao, Yi