Dirac-type problems for hypergraphs

Georgia State University Research Foundation, Inc., Atlanta GA

Investigators

Abstract

Although Combinatorics is as old as human's ability to count, its most impressive growth has been seen only in recent decades, mainly due to the rapid development of computer science. Extremal Combinatorics 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. The proposed research concentrates on extremal problems for hypergraphs. Since hypergraphs have more complicated structures than graphs, generalizing results from graphs to hypergraphs is usually far from straightforward and frequently gives rise to new phenomena. For example, there are multiple ways (depending on how to define degrees and cycles in hypergraphs) to extend the classical result of Dirac on Hamilton cycles to hypergraphs -- none of them has an easy proof. The Dirac problems, and related matching and packing problems have received considerable attention lately. Modern tools, e.g., the absorbing method and the regularity method, have helped to generate new results, and yet many fundamental problems in the area remain unsolved. The PI plans to tackle many outstanding problems in the area, developing the extremal theory of hypergraphs.