图与超图分解及谱形式极值问题

The problem of H-decomposition of graphs or hypergraphs has tight relationship with Turán type extremal problems, both of them are fundamental problems in extremal graph theory, the study of the spectral extremal graph theory provides new ideas for the study of the corresponding Turán type extremal problems. The project mainly concerns the conjecture of Pikhurko-Sousa related to H-decomposition of graphs, the H-decomposition of hypergraphs and the spectral versions of some extremal problems. We want to solve the conjecture of Pikhurko-Sousa when H is vertex-critical and then solve the conjecture completely, solve the H-decomposition problem when H is degenerate and find the general function for the H-decomposition of hypergrapgs when H is nondegenerate, solve two conjectures related to the spectral extremal graph theory proposed by Nikiforov. The solvement of those problems will improve the developement of the extremal graph theory.

图或超图的H-分解问题和Turán型极值问题关系非常紧密，都是极值图论研究中的基本问题，而极值问题谱形式为Turán型极值问题研究提供了新的思路和角度。本项目主要围绕图的H-分解的Pikhurko-Sousa猜想（当H色数大于等于3时，n阶图的H-分解的极图边数等于以H为限制子图的n阶极图边数），超图的H-分解问题和极值问题谱形式开展研究。希望证明Pikhurko-Sousa猜想当H为点临界图时成立，进而完全证明该猜想；解决H为退化情形时超图的H-分解问题并探索H为非退化情形时超图H-分解的一般公式；解决Nikiforov提出的有关极值问题谱形式的两个猜想。这些问题的解决和取得进展必然会促进极值图论理论的完善和发展。

本项目以图与超图的分解及谱形式极值问题为研究主题，在图与超图的分解问题，图兰型问题，谱形式极值问题，图的划分问题及图论应用方面取得重要进展，所得研究成果超出预期，圆满完成了项目研究任务和目标。主要成果包括证明了Pikhurko-Sousa猜想对一类非（色数）临界图成立； 证明了Fuller和Gould 提出的关于K_4^-边谱的猜想；证明了Mycroft猜想对广义4圈是对的，并且为该猜想找到了反例；解决了 Falgas-Ravry 和Zhao (SIAM J. Discrete Math., 2016)提出的超图覆盖的公开问题；证明了Jaeger的关于模定向的著名猜想等价于其二部简单图形式，证明了关于模定向的Ramsey型定理；证明了Nikiforov猜想的一个弱版本；证明了Nikiforov猜想对直径不超过4的树都成立；在图论应用方面，提出了一种新的图元采样算法SSRW，在保持当前最好精度的情况下，顺利地将图元采样算法扩展到了高阶图元上面。这些结果以学术论文形式发表在专业权威和重要的学术刊物包括”Advances in Mathematics”, “J. Graph Theory”,“ J. Combin. Theory Ser. A”, “J. Combin. Theory Ser B”, “SIAM J. Discrete Math.”，“Linear Algebra Appl.”, “Discrete Math.”等及计算机领域顶级会议上。这些结果或者解决了未知猜想或者在这些猜想和问题上取得了重要进展，这些结果的获得丰富和拓展了图论的研究领域。