Teachers of BIT have achieved results in the graph factor research

News resources & Photographer: School of Mathematics and Statistics

Editor: Wang Huan

Translator: News Agency of BIT


Recently, Professor Han Jie from School of Mathematics and Statistics, Beijing Institute of Technology, has consecutively published two research papers entitled “Tiling multipartite hypergraphs in Quasi-random Hypergraphs” and “Embedding clique-factors in graphs with low 1-independence number” in the international authoritative journal Journal of Combinatorial Theory, Series B. These two papers study the existence of F factors in graphs with certain randomness and hypergraphs, giving the asymptotically optimal degree conditions and density conditions.

Given a graph G, an F factor refers to all vertices of F covering G with multiple vertices non-overlapping. When F is an edge, the F factor is also made as a perfect match. The famous Hajnal-Szemerédi theorem gives the optimal degree condition for the guaranteed group factor in the graph. In addition to the perfectly matched case, determining whether a graph has an F factor is the well-known NP perfect problem. For decades, the existence of F factors in graphs and hypergraphs has been a central problem in the field of graph theory. This problem has more complete results in both classical dense graphs and classical random graphs. In recent years, studies on this problem have focused on graphs with certain (but weak) randomness and hypergraphs. One direction of this research is to consider the case that the independent number of the graph is sublinear (there is no linear-sized independent set), and the other is to consider the quasi-random hypergraph with very weak randomness.

In the latest research, Han Jie, the team of Professor Wang Guanghui of Shandong University and Professor JaehoonKim of Korea Academy of Science and Technology decided the optimality condition for the existence of group factors in independent linear graphs, and rejected the assumption put forward by predecessors. In another study, Han Jie, teacher Ding Laihao from Central China Normal University and the team of Professor Wang Guanghui from Shandong University studied the optimal density of the existence of degenerate F factors in the quasi-random hypergraph and obtained a series of results. The density (upper) bound obtained for the 3.png factor problem about the 3-consistent hypergraph matches the lower bound obtained by the famous mathematician Mubayi in 2016.

In these two studies, the authors are listed in alphabetical order, and Professor Han Jie is the corresponding author in both cases.

Paper link:

Attached research team and individual profiles:

Han Jie, professor, main member of the graph theory combination team of the School of Mathematics and Statistics, BIT, professional responsibility professor of graph theory and combination optimization discipline. He graduated with a bachelor's degree from BIT and a doctor's degree from Georgia State University. He has been engaged in the research work of graph theory portfolio and computer theory for a long time. In 2019, he was awarded a grant from the Simons Foundation Fund of the United States, and was selected into the National High-level Young Talents Program in 2022. He has published 4 academic papers in several comprehensive authoritative journals of mathematics like Transactions of the American Mathematical Society, International Mathematics Research Notice, Journal of London Mathematical Society, 9 papers in top graph theory journals like Journal of Combinatorial Theory, Series B, and 5 papers in the top computer theory conferences like SODA and ICALP.