Extremal Combinatorics under Degree Conditions

Georgia State University Research Foundation, Inc., Atlanta GA

Investigators

Abstract

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.